<html>
<head>
<title>C++ Annotations Version 6.5.0</title>
</head>
<body text="black" bgcolor="white">
<hr>
<ul>
    <li> <a href="cplusplus.html">Table of Contents</a>
    <li> <a href="cplusplus16.html">Previous Chapter</a>
    <li> <a href="cplusplus18.html">Next Chapter</a>
</ul>
<hr>
<a name="STL"></a><a name="l228"></a>
<h1>Chapter 17: The Standard Template Library, generic algorithms</h1>
<a name="stl"></a>
<blockquote>
    <em>
        Don't hesitate to send in feedback: send an e-mail if you like the
        C++ Annotations; if you think that important material was omitted;
        if you find errors or typos in the text or the code examples;
        or if you just feel like e-mailing. Send your e-mail to
        <a href="mailto:f.b.brokken@rug.nl">Frank B. Brokken</a>.
<p>
<strong>Please</strong> state the document version you're referring to, as found in
        the title (in this document: 6.5.0) and please state chapter and
        paragraph name or number you're referring to.
<p>
All received mail is processed conscientiously, and received
        suggestions for improvements will usually have been processed by the
        time a new version of the Annotations is released. Except for the
        incidental case I will normally not acknowledge the receipt of
        suggestions for improvements. Please don't interpret this as me not
        appreciating your efforts.
    </em>
</blockquote>
<p>
<a name="stl/intro.yo"></a>The <a name="an2167"></a>
<code>Standard Template Library</code> (<a name="an2168"></a>
STL) is a <a name="an2169"></a>
general purpose library
consisting of <a name="an2170"></a>
containers,
    <a name="an2171"></a>
generic algorithms, <a name="an2172"></a>
iterators, <a name="an2173"></a>
function objects,
    allocators, <a name="an2174"></a>
adaptors and <a name="an2175"></a>
data structures. The data structures used
in the algorithms are <em>abstract</em> in the sense that the algorithms can be
used on (practically) every data type.
<p>
The algorithms can work on these <a name="an2176"></a>
abstract data types due to the fact that
they are <a name="an2177"></a>
<em>template</em> based algorithms. In this chapter the <em>construction</em>
of templates is not discussed (see chapter <a href="cplusplus18.html#TEMPLATES">18</a> for that). Rather,
this chapter focuses on the <em>use</em> of these template algorithms.
<p>
Several parts of the standard template library have already been discussed in
the <strong>C++</strong> Annotations. In chapter <a href="cplusplus12.html#Containers">12</a> the abstract containers
were discussed, and in section <a href="cplusplus09.html#FUNOBJ">9.10</a> function objects were introduced.
Also, <em>iterators</em> were mentioned at several places in this
document.
<p>
The remaining components of the STL will be covered in this
chapter. Iterators, adaptors and generic algorithms will be discussed in the
coming sections. <em>Allocators</em> take care of the memory allocation within the
STL. The default <a name="an2178"></a>
allocator class suffices for most applications, and is
not further discussed in the <strong>C++</strong> Annotations.
<p>
Forgetting to delete <a name="an2179"></a>
allocated memory is a common source of errors or
memory leaks in a program. The <a name="an2180"></a>
<code>auto_ptr</code> template class may be used to
prevent these types of problems. The <code>auto_ptr</code> class is discussed in
section <a href="cplusplus17.html#AUTOPTR">17.3</a>.
<p>
All elements of the STL are defined in the standard namespace. Therefore, a
<code>using namespace std</code> or comparable directive is required unless it is
preferred to specify the required namespace explicitly. This occurs in at
least one situation: in header files no <code>using</code> directive should be used,
so here the <code>std::</code> scope specification should always be specified when
referring to elements of the STL.
<p>
<a name="PREDEFINED"></a><a name="l229"></a>
<h2>17.1: Predefined function objects</h2>
<a name="stl/predefined"></a>Function objects play important roles in combination with generic
algorithms. For example, there exists a <a name="an2181"></a>
generic algorithm <code>sort()</code>
expecting two iterators defining the range of objects that should be sorted,
as well as a function object calling the appropriate comparison operator for
two objects. Let's take a quick look at this situation. Assume strings are
stored in a vector, and we want to sort the vector in descending order. In
that case, sorting the vector <code>stringVec</code> is as simple as:
            <pre>
        sort(stringVec.begin(), stringVec.end(), greater&lt;std::string&gt;());
</pre>
    The last argument is recognized as a <a name="an2182"></a>
<em>constructor</em>: it is an
<a name="an2183"></a>
<em>instantiation</em> of the <a name="an2184"></a>
<code>greater&lt;&gt;()</code> template class, applied to
<code>strings</code>. This object is called as a <a name="an2185"></a>
function object by the <code>sort()</code>
generic algorithm. It will call the <a name="an2186"></a>
<code>operator&gt;()</code> of the provided data type
(here <a name="an2187"></a>
<code>std::string</code>) whenever its <a name="an2188"></a>
<code>operator()()</code> is called. Eventually,
when <code>sort()</code> returns, the first element of the vector will be the greatest
element.
<p>
The <code>operator()()</code> (<a name="an2189"></a>
function call operator) itself is <em>not</em> visible
at this point: don't confuse the parentheses in <code>greater&lt;string&gt;()</code> with
calling <code>operator()()</code>. When that operator is actually used inside
<code>sort()</code>, it receives two arguments: two strings to compare for
`greaterness'. Internally, the <a name="an2190"></a>
<code>operator&gt;()</code> of the data type to which the
iterators point (i.e., <code>string</code>) is called by <code>greater&lt;string&gt;</code>'s function
operator (<code>operator()()</code>) to compare the two objects. Since <code>greater&lt;&gt;</code>'s
function call operator is defined <a name="an2191"></a>
inline, the call itself is not actually
present in the code. Rather, <code>sort()</code> calls <code>string::operator&gt;()</code>,
thinking it called <code>greater&lt;&gt;::operator()()</code>.
<p>
Now that we know that a constructor is passed as argument to (many) generic
algorithms, we can design our own function objects. Assume we want to sort our
vector case-insensitively. How do we proceed? First we note that the default
<code>string::operator&lt;()</code> (for an incremental sort) is not appropriate, as it
does <a name="an2192"></a>
case sensitive comparisons. So, we provide our own <code>case_less</code>
class, in which the two strings are compared case insensitively. Using the
standard <strong>C</strong> function <a name="an2193"></a>
<code>strcasecmp()</code>, the following program performs the
trick. It sorts its command-line arguments in ascending alphabetical order:
                  <pre>
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;algorithm&gt;

    using namespace std;

    class case_less
    {
        public:
            bool operator()(string const &amp;left, string const &amp;right) const
            {
                return strcasecmp(left.c_str(), right.c_str()) &lt; 0;
            }
    };

    int main(int argc, char **argv)
    {
        sort(argv, argv + argc, case_less());
        for (int idx = 0; idx &lt; argc; ++idx)
            cout &lt;&lt; argv[idx] &lt;&lt; " ";
        cout &lt;&lt; endl;
    }
</pre>
    The <a name="an2194"></a>
default constructor of the <code>class case_less</code> is used with
<code>sort()</code>'s final argument. Therefore, the only member function that must be
defined with the class <code>case_less</code> is the function object operator
<code>operator()()</code>. Since we know it's called with <code>string</code> arguments, we
define it to expect two <code>string</code> arguments, which are used in the
<code>strcasecmp()</code> function. Furthermore, the <code>operator()()</code> function is made
<a name="an2195"></a>
inline, so that it does not produce overhead when called by  the <code>sort()</code>
function. The <code>sort()</code> function calls the function object with various
combinations of <code>strings</code>, i.e., it <em>thinks</em> it does so. However, in fact
it calls <code>strcasecmp()</code>, due to the inline-nature of
<code>case_less::operator()()</code>.
<p>
The comparison function object is often a <a name="an2196"></a>

<em>predefined function object</em>, since these are available for many commonly
used operations.  In the following sections the available predefined function
objects are presented, together with some examples showing their use. At the
end of the section about function objects <a name="an2197"></a>
<em>function adaptors</em> are
introduced. Before predefined function objects can be used the following
preprocessor directive must have been specified: <a name="an2198"></a>

        <pre>
    #include &lt;functional&gt;
</pre>
    Predefined function objects are used predominantly with generic
algorithms. Predefined function objects exists for arithmetic, relational, and
logical operations. In section <a href="cplusplus20.html#BITFUN">20.4</a> predefined function objects are
developed performing <a name="an2199"></a>
bitwise operations.
<p>
<a name="l230"></a>
<h3>17.1.1: Arithmetic function objects</h3>
    <a name="stl/arithmetic.yo"></a>The <a name="an2200"></a>
 arithmetic function objects support the
standard <a name="an2201"></a>
arithmetic operations: <a name="an2202"></a>
addition, <a name="an2203"></a>
subtraction,
<a name="an2204"></a>
multiplication, <a name="an2205"></a>
division, <a name="an2206"></a>
modulus and <a name="an2207"></a>
negation. These predefined
arithmetic function objects invoke the corresponding operator of the
associated data type. For example, for addition the function object
<code>plus&lt;Type&gt;</code> <a name="an2208"></a>
 is available. If we set <code>type</code> to <code>size_t</code>
then the <code>+</code> operator for <code>size_t</code> values is used, if we set <code>type</code> to
<code>string</code>, then the <code>+</code> operator for strings is used. For example:
        <pre>
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;functional&gt;
    using namespace std;

    int main(int argc, char **argv)
    {
        plus&lt;size_t&gt; uAdd;       // function object to add size_ts

        cout &lt;&lt; "3 + 5 = " &lt;&lt; uAdd(3, 5) &lt;&lt; endl;

        plus&lt;string&gt; sAdd;       // function object to add strings

        cout &lt;&lt; "argv[0] + argv[1] = " &lt;&lt; sAdd(argv[0], argv[1]) &lt;&lt; endl;
    }
    /*
        Generated output with call: a.out going

        3 + 5 = 8
        argv[0] + argv[1] = a.outgoing
    */
</pre>
    Why is this useful? Note that the function object can be used with all
kinds of data types (not only with the predefined datatypes), in which the
particular operator has been overloaded. Assume that we want to perform an
operation on a common variable on the one hand and, on the other hand, in turn
on each element of an array. E.g., we want to compute the sum of the elements
of an array; or we want to concatenate all the strings in a text-array. In
situations like these the function objects come in handy. As noted before, the
function objects are heavily used in the context of the generic algorithms, so
let's take a quick look ahead at one of them.
<p>
One of the generic algorithms is called <a name="an2209"></a>
<code>accumulate()</code>. It visits all
elements implied by an iterator-range, and performs a requested binary
operation on a common element and each of the elements in the range, returning
the accumulated result after visiting all elements.
For example, the following program accumulates all command line arguments,
and prints the final string:
        <pre>
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;functional&gt;
    #include &lt;numeric&gt;
    using namespace std;

    int main(int argc, char **argv)
    {
        string result =
                accumulate(argv, argv + argc, string(), plus&lt;string&gt;());

        cout &lt;&lt; "All concatenated arguments: " &lt;&lt; result &lt;&lt; endl;
    }
</pre>
    The first two arguments define the (iterator) range of elements to visit,
the third argument is <code>string()</code>. This anonymous string object provides an
initial value. It could as well have been initialized to
        <pre>
        string("All concatenated arguments: ")
</pre>
    in which case the <code>cout</code> statement could have been a simple
        <pre>
    cout &lt;&lt; result &lt;&lt; endl;
</pre>
    Then, the operator to apply is <code>plus&lt;string&gt;()</code>. Note here that a
constructor is called: it is <em>not</em> <code>plus&lt;string&gt;</code>, but rather
<code>plus&lt;string&gt;()</code>. The final concatenated string is returned.
<p>
Now we define our own class <code>Time</code>, in which the
<a name="an2210"></a>
<code>operator+()</code> has been overloaded. Again, we can apply the predefined
function object <code>plus</code>, now tailored to our newly defined datatype, to add
times:
        <pre>
    #include &lt;iostream&gt;
    #include &lt;sstream&gt;
    #include &lt;string&gt;
    #include &lt;vector&gt;
    #include &lt;functional&gt;
    #include &lt;numeric&gt;

    using namespace std;

    class Time
    {
        friend ostream &amp;operator&lt;&lt;(ostream &amp;str, Time const &amp;time)
        {
            return cout &lt;&lt; time.d_days &lt;&lt; " days, " &lt;&lt; time.d_hours &lt;&lt;
                                                        " hours, " &lt;&lt;
                            time.d_minutes &lt;&lt; " minutes and " &lt;&lt;
                            time.d_seconds &lt;&lt; " seconds.";
        }

        size_t d_days;
        size_t d_hours;
        size_t d_minutes;
        size_t d_seconds;

        public:
            Time(size_t hours, size_t minutes, size_t seconds)
            :
                d_days(0),
                d_hours(hours),
                d_minutes(minutes),
                d_seconds(seconds)
            {}
            Time &amp;operator+=(Time const &amp;rValue)
            {
                d_seconds   += rValue.d_seconds;
                d_minutes   += rValue.d_minutes   + d_seconds / 60;
                d_hours     += rValue.d_hours     + d_minutes / 60;
                d_days      += rValue.d_days      + d_hours   / 24;
                d_seconds   %= 60;
                d_minutes   %= 60;
                d_hours     %= 24;

                return *this;
            }
    };
    Time const operator+(Time const &amp;lValue, Time const &amp;rValue)
    {
        return Time(lValue) += rValue;
    }

    int main(int argc, char **argv)
    {
        vector&lt;Time&gt; tvector;

        tvector.push_back(Time( 1, 10, 20));
        tvector.push_back(Time(10, 30, 40));
        tvector.push_back(Time(20, 50,  0));
        tvector.push_back(Time(30, 20, 30));

        cout &lt;&lt;
            accumulate
            (
                tvector.begin(), tvector.end(), Time(0, 0, 0), plus&lt;Time&gt;()
            ) &lt;&lt;
            endl;
    }
    /*
        produced output:

        2 days, 14 hours, 51 minutes and 30 seconds.
    */
</pre>
    Note that all member functions of <code>Time</code> in the above source are inline
functions. This approach was followed in order to keep the example relatively
small and to show explicitly that the <code>operator+=()</code> function may be an
inline function. On the other hand, in real life <code>Time</code>'s <code>operator+=()</code>
should probably not be made inline, due to its size.
<p>
Considering the previous discussion of the <code>plus</code> function object, the
example is pretty straightforward. The class <code>Time</code> defines a constructor,
it defines an insertion operator and it defines its own <code>operator+()</code>,
adding two time objects.
<p>
In <code>main()</code>  four <code>Time</code> objects are stored in a
<code>vector&lt;Time&gt;</code> object. Then, the <code>accumulate()</code> generic algorithm is
called to compute the accumulated time. It returns a <code>Time</code> object, which
is inserted in the <code>cout ostream</code> object.
<p>
While the first example did show the use of a <em>named</em> function object,
the last two examples showed the use of  <a name="an2211"></a>
<em>anonymous</em> objects which were
passed to the (<code>accumulate()</code>) function.
<p>
The following arithmetic objects are available as predefined objects:
    <ul>
    <li><a name="an2212"></a>
<code>plus&lt;&gt;()</code>: as shown, this object's <code>operator()()</code> member calls
<code>operator+()</code> as a <a name="an2213"></a>
binary operator, passing it its two parameters,
returning <code>operator+()</code>'s return value.
    <li><a name="an2214"></a>
<code>minus&lt;&gt;()</code>: this object's <code>operator()()</code> member calls
<a name="an2215"></a>
<code>operator-()</code> as a binary operator, passing it its two parameters and
returning <code>operator-()</code>'s return value.
    <li><a name="an2216"></a>
<code>multiplies&lt;&gt;()</code>: this object's <code>operator()()</code> member calls
<a name="an2217"></a>
<code>operator*()</code> as a binary operator, passing it its two parameters and
returning <code>operator*()</code>'s return value.
    <li><a name="an2218"></a>
<code>divides&lt;&gt;()</code>: this object's <code>operator()()</code> member calls
<a name="an2219"></a>
<code>operator/()</code>, passing it its two parameters and
returning <code>operator/()</code>'s return value.
    <li><a name="an2220"></a>
<code>modulus&lt;&gt;()</code>: this object's <code>operator()()</code> member calls
<a name="an2221"></a>
<code>operator%()</code>, passing it its two parameters and
returning <code>operator%()</code>'s return value.
    <li><a name="an2222"></a>
<code>negate&lt;&gt;()</code>: this object's <code>operator()()</code> member calls
<code>operator-()</code> as a unary operator, passing it its  parameter and
returning the unary <code>operator-()</code>'s return value.
    </ul>
    An example using the unary <code>operator-()</code> follows, in
which the <a name="an2223"></a>
<code>transform()</code> generic algorithm is used to toggle the signs of all
elements in an array. The <code>transform()</code> generic algorithm expects two
iterators, defining the range of objects to be transformed, an iterator
defining the begin of the destination range (which may be the same iterator as
the first argument) and a function object defining a unary operation for the
indicated data type.
        <pre>
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;functional&gt;
    #include &lt;algorithm&gt;
    using namespace std;

    int main(int argc, char **argv)
    {
        int iArr[] = { 1, -2, 3, -4, 5, -6 };

        transform(iArr, iArr + 6, iArr, negate&lt;int&gt;());

        for (int idx = 0; idx &lt; 6; ++idx)
            cout &lt;&lt; iArr[idx] &lt;&lt; ", ";

        cout &lt;&lt; endl;
    }
    /*
        Generated output:

        -1, 2, -3, 4, -5, 6,
    */
</pre>
<p>
<a name="l231"></a>
<h3>17.1.2: Relational function objects</h3>
    <a name="stl/relational.yo"></a>The relational operators <a name="an2224"></a>
 are called by the
<a name="an2225"></a>
 relational function objects. All standard
relational operators are supported: <code>==, !=, &gt;, &gt;=, &lt;</code> and <code>&lt;=</code>. The
following objects are available:
    <ul>
    <li><a name="an2226"></a>
<code>equal_to&lt;&gt;()</code>: this object's <code>operator()()</code> member calls
<a name="an2227"></a>
<code>operator==()</code> as a binary operator, passing it its two parameters and
returning <code>operator==()</code>'s return value.
    <li><a name="an2228"></a>
<code>not_equal_to&lt;&gt;()</code>: this object's <code>operator()()</code> member calls
<a name="an2229"></a>
<code>operator!=()</code> as a binary operator, passing it its two parameters and
returning <code>operator!=()</code>'s return value.
    <li><a name="an2230"></a>
<code>greater&lt;&gt;()</code>: this object's <code>operator()()</code> member calls
<a name="an2231"></a>
<code>operator&gt;()</code> as a binary operator, passing it its two parameters and
returning <code>operator&gt;()</code>'s return value.
    <li><a name="an2232"></a>
<code>greater_equal&lt;&gt;()</code>: this object's <code>operator()()</code> member calls
<a name="an2233"></a>
<code>operator&gt;=()</code> as a binary operator, passing it its two parameters and
returning <code>operator&gt;=()</code>'s return value.
    <li><a name="an2234"></a>
<code>less&lt;&gt;()</code>: this object's <code>operator()()</code> member calls
<a name="an2235"></a>
<code>operator&lt;()</code> as a binary operator, passing it its two parameters and
returning <code>operator&lt;()</code>'s return value.
    <li><a name="an2236"></a>
<code>less_equal&lt;&gt;()</code>: this object's <code>operator()()</code> member calls
<a name="an2237"></a>
<code>operator&lt;=()</code> as a binary operator, passing it its two parameters and
returning <code>operator&lt;=()</code>'s return value.
    </ul>
    Like the arithmetic function objects, these function objects can be used
as <em>named</em> or as <a name="an2238"></a>
<em>anonymous</em> objects. An example using the relational
function objects using the generic algorithm <a name="an2239"></a>
<code>sort()</code> is:
        <pre>
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;functional&gt;
    #include &lt;algorithm&gt;
    using namespace std;

    int main(int argc, char **argv)
    {
        sort(argv, argv + argc, greater_equal&lt;string&gt;());

        for (int idx = 0; idx &lt; argc; ++idx)
            cout &lt;&lt; argv[idx] &lt;&lt; " ";
        cout &lt;&lt; endl;

        sort(argv, argv + argc, less&lt;string&gt;());

        for (int idx = 0; idx &lt; argc; ++idx)
            cout &lt;&lt; argv[idx] &lt;&lt; " ";
        cout &lt;&lt; endl;
    }
</pre>
    The <code>sort()</code> generic algorithm expects an iterator range and a
<a name="an2240"></a>
comparator of the data type to which the iterators point. The example shows
the
    <a name="an2241"></a>
alphabetic sorting of strings and the <a name="an2242"></a>
reversed sorting of
strings. By passing <code>greater_equal&lt;string&gt;()</code> the strings are sorted in
<em>decreasing</em> order (the first word will be the 'greatest'), by passing
<code>less&lt;string&gt;()</code> the strings are sorted in <em>increasing</em> order (the first
word will be the 'smallest').
<p>
Note that the type of the elements of <code>argv</code> is <code>char *</code>, and that the
relational function object expects a <code>string</code>. The relational object
<code>greater_equal&lt;string&gt;()</code> will therefore use the <code>&gt;=</code> operator of strings,
but will be called with <code>char *</code> variables. The promotion from <code>char const
*</code> to <code>string</code> is performed silently.
<p>
<a name="l232"></a>
<h3>17.1.3: Logical function objects</h3>
    <a name="stl/logical.yo"></a>The <a name="an2243"></a>
logical operators <a name="an2244"></a>
 are called by the
    <a name="an2245"></a>
 logical function objects. The standard logical
operators are supported: <code>and, or,</code> and <code>not</code>. The following objects are
available:
    <ul>
    <li><a name="an2246"></a>
<code>logical_and&lt;&gt;()</code>: this object's <code>operator()()</code> member calls
<a name="an2247"></a>
<code>operator&amp;&amp;()</code> as a binary operator, passing it its two parameters and
returning <code>operator&amp;&amp;()</code>'s return value.
    <li><a name="an2248"></a>
<code>logical_or&lt;&gt;()</code>: this object's <code>operator()()</code> member calls
<a name="an2249"></a>
<code>operator||()</code> as a binary operator, passing it its two parameters and
returning <code>operator||()</code>'s return value.
    <li><a name="an2250"></a>
<code>logical_not&lt;&gt;()</code>:  this object's <code>operator()()</code> member calls
<code>operator!()</code> as a unary operator, passing it its  parameter and
returning the unary <code>operator!()</code>'s return value.
    </ul>
    An example using <code>operator!()</code> is provided in the following trivial
program, in which the <a name="an2251"></a>
<code>transform()</code> generic algorithm is used to transform
the logical values stored in an array:
        <pre>
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;functional&gt;
    #include &lt;algorithm&gt;
    using namespace std;

    int main(int argc, char **argv)
    {
        bool bArr[] = {true, true, true, false, false, false};
        size_t const bArrSize = sizeof(bArr) / sizeof(bool);

        for (size_t idx = 0; idx &lt; bArrSize; ++idx)
            cout &lt;&lt; bArr[idx] &lt;&lt; " ";
        cout &lt;&lt; endl;

        transform(bArr, bArr + bArrSize, bArr, logical_not&lt;bool&gt;());

        for (size_t idx = 0; idx &lt; bArrSize; ++idx)
            cout &lt;&lt; bArr[idx] &lt;&lt; " ";
        cout &lt;&lt; endl;
    }
    /*
        generated output:

        1 1 1 0 0 0
        0 0 0 1 1 1
    */
</pre>
<p>
<a name="l233"></a>
<h3>17.1.4: Function adaptors</h3>
    <a name="stl/adaptors.yo"></a>Function adaptors modify the working of existing function objects. There are
two kinds of <a name="an2252"></a>
function adaptors:
    <ul>
    <li> <em>Binders</em> <a name="an2253"></a>
 are function adaptors converting binary
function objects to unary function objects. They do so by <em>binding</em> one
object to a <a name="an2254"></a>
constant function object. For example, with the
<code>minus&lt;int&gt;()</code> function object, which is a <a name="an2255"></a>
binary function object, the
first argument may be bound to 100, meaning that the resulting value will
always be <code>100</code> minus the value of the second argument. Either the first or
the second argument may be bound to a specific value. To bind the first
argument to a specific value, the function object <a name="an2256"></a>
<code>bind1st()</code> is used. To
bind the second argument of a binary function to a specific value
<a name="an2257"></a>
<code>bind2nd()</code> is used. As an example, assume we want to count all elements of
a vector of <code>Person</code> objects that exceed (according to some criterion) some
reference <code>Person</code> object. For this situation we pass the following binder
and <a name="an2258"></a>
relational function object to the <a name="an2259"></a>
<code>count_if()</code> generic algorithm:
        <pre>
    bind2nd(greater&lt;Person&gt;(), referencePerson)
</pre>
    What would such a binder do? First of all, it's a function object, so it
needs <code>operator()()</code>. Next, it expects two arguments: a reference to another
function object and a fixed operand. Although binders are defined as
templates, it is illustrative to have a look at their implementations,
assuming they were straight functions. Here is such a pseudo-implementation of
a binder:
        <pre>
    class bind2nd
    {
        FunctionObject const &amp;d_object;
        Operand const &amp;d_rvalue;
        public:
            bind2nd(FunctionObject const &amp;object, Operand const &amp;operand);
            ReturnType operator()(Operand const &amp;lvalue);
    };
    inline bind2nd::bind2nd(FunctionObject const &amp;object, 
                            Operand const &amp;operand)
    :
        d_object(object),
        d_operand(operand)
    {}
    inline ReturnType bind2nd::operator()(Operand const &amp;lvalue)
    {
        return d_object(lvalue, d_rvalue);
    }
</pre>
    When its <code>operator()()</code> member is called the binder merely passes the
call to the object's <code>operator()()</code>, providing it with two arguments: the
<code>lvalue</code> it itself received and the fixed operand it received via its
constructor. Note the simplicity of these kind of classes: all its members can
usually be implemented inline.
<p>
The <code>count_if()</code> generic algorithm visits all the elements in an
iterator range, returning the number of times the <a name="an2260"></a>
predicate specified as
its final argument returns <a name="an2261"></a>
<code>true</code>. Each of the elements of the iterator
range is given to the predicate, which is therefore a <a name="an2262"></a>
unary function. By
using the binder the binary function object <code>greater()</code> is adapted to a
unary function object, comparing each of the elements in the range to the
reference person.  Here is, to be complete, the call of the <code>count_if()</code>
function:
        <pre>
    count_if(pVector.begin(), pVector.end(),
        bind2nd(greater&lt;Person&gt;(), referencePerson))
</pre>
    <li> <em>Negators</em> <a name="an2263"></a>
 are function adaptors converting the
<a name="an2264"></a>
truth value of a <a name="an2265"></a>
predicate function. Since there are unary and binary
predicate functions, there are two negator function adaptors: <a name="an2266"></a>
<code>not1()</code> is
the negator  used with <a name="an2267"></a>
unary function objects, <a name="an2268"></a>
<code>not2()</code> is the
negator  used with <a name="an2269"></a>
binary function objects.
    </ul>
    If we want to count the number of persons in a <code>vector&lt;Person&gt;</code> vector
<em>not</em> exceeding a certain reference person, we may, among other approaches,
use either of the following alternatives:
    <ul>
    <li> Use a binary predicate that directly offers the required comparison:
        <pre>
    count_if(pVector.begin(), pVector.end(),
        bind2nd(less_equal&lt;Person&gt;(), referencePerson))
</pre>
    <li> Use <code>not2</code> combined with the <code>greater()</code> predicate:
        <pre>
    count_if(pVector.begin(), pVector.end(),
        bind2nd(not2(greater&lt;Person&gt;()), referencePerson))
</pre>
        Note that <code>not2()</code> is a negator negating the truth value of a binary
<code>operator()()</code> member: it must be used to wrap the binary predicate
<code>greater&lt;Person&gt;()</code>, negating its truth value.
    <li> Use <code>not1()</code> combined with the <code>bind2nd()</code> predicate:
        <pre>
    count_if(pVector.begin(), pVector.end(),
        not1(bind2nd(greater&lt;Person&gt;(), referencePerson)))
</pre>
        Note that <code>not1()</code> is a negator negating the truth value of a unary
<code>operator()()</code> member: it is used to wrap the unary predicate <code>bind2nd()</code>,
negating its truth value.
<p>
The following little example illustrates the use of negator function
adaptors, completing the section on function objects:
        <pre>
    #include &lt;iostream&gt;
    #include &lt;functional&gt;
    #include &lt;algorithm&gt;
    #include &lt;vector&gt;
    using namespace std;

    int main(int argc, char **argv)
    {
        int iArr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

        cout &lt;&lt; count_if(iArr, iArr + 10, bind2nd(less_equal&lt;int&gt;(), 6)) &lt;&lt;
            endl;
        cout &lt;&lt; count_if(iArr, iArr + 10, bind2nd(not2(greater&lt;int&gt;()), 6)) &lt;&lt;
            endl;
        cout &lt;&lt; count_if(iArr, iArr + 10, not1(bind2nd(greater&lt;int&gt;(), 6))) &lt;&lt;
            endl;
    }
    /*
        produced output:

        6
        6
        6
    */
</pre>
    </ul>
    One may wonder which of these alternative approaches is fastest. Using the
first approach, in which a  directly available function object was used, two
actions must be performed for each iteration by <code>count_if()</code>:
    <ul>
    <li> The binder's <code>operator()()</code> is called;
    <li> The operation <code>&lt;=</code> is performed for <code>int</code> values.
    </ul>
    Using the second approach, in which the <code>not2</code> negator is used to
negate the truth value of the complementary logical function adaptor, three
actions must be performed for each iteration by <code>count_if()</code>:
    <ul>
    <li> The binder's <code>operator()()</code> is called;
    <li> The negator's <code>operator()()</code> is called;
    <li> The operation <code>&gt;</code> is performed for <code>int</code> values.
    </ul>
    Using the third approach, in which a <code>not1</code> negator is used to
negate the truth value of the binder, three
actions must be performed for each iteration by <code>count_if()</code>:
    <ul>
    <li> The negator's <code>operator()()</code> is called;
    <li> The binder's <code>operator()()</code> is called;
    <li> The operation <code>&gt;</code> is performed for <code>int</code> values.
    </ul>
    From this, one might deduce that the first approach is fastest. Indeed,
using Gnu's <code>g++</code> compiler on an old, 166 MHz pentium, performing 3,000,000
<code>count_if()</code> calls for each variant, shows the first approach requiring
about 70% of the time needed by the other two approaches to complete.
<p>
However, these differences disappear if the compiler is instructed to
optimize for speed (using the <a name="an2270"></a>
<code>-O6</code> <a name="an2271"></a>
 compiler
flag). When interpreting these results one should keep in mind that multiple
nested function calls are merged into a single function call if the
implementations of these functions are given inline and if the compiler
follows the suggestion to implement these functions as true inline functions
indeed.  If this is happening, the three approaches all merge to a single
operation: the comparison between two <code>int</code> values. It is likely that the
compiler does so when asked to optimize for speed.
<p>
<a name="ITERATORS"></a><a name="l234"></a>
<h2>17.2: Iterators</h2>
<a name="stl/iterators"></a>Iterators are objects acting like <a name="an2272"></a>
pointers. Iterators have the following
general  <a name="an2273"></a>
 characteristics:
    <ul>
    <li> Two iterators may be compared for (in)equality using the <code>==</code> and
<code>!=</code> operators. Note that the <em>ordering</em> operators (e.g., <code>&gt;</code>, <code>&lt;</code>)
normally cannot be used.
    <li> Given an iterator <code>iter</code>, <code>*iter</code> represents the object the
iterator points to (alternatively, <code>iter-&gt;</code> can be used to reach the members
of the object the iterator points to).
    <li> <code>++iter</code> or <code>iter++</code> advances the iterator to the next
element. The notion of advancing an iterator to the next element is
consequently applied: several containers have a <a name="an2274"></a>
<em>reversed_iterator</em> type, in
which the <code>iter++</code> operation actually reaches a <a name="an2275"></a>
previous element in a
sequence.
    <li> <em>Pointer arithmetic</em> may be used with containers having their
elements stored consecutively in memory. This includes the <a name="an2276"></a>
<code>vector</code> and
<a name="an2277"></a>
<code>deque</code>. For these containers <code>iter + 2</code> points to the second element
beyond the one to which <code>iter</code> points.
    <li> An interator which is merely defined is comparable to a
        <a name="an2278"></a>
 0-pointer, as shown by the following little
example:
        <pre>
    #include &lt;vector&gt;
    #include &lt;iostream&gt;
    using namespace std;

    int main()
    {
        vector&lt;int&gt;::iterator vi;

        cout &lt;&lt; &amp;*vi &lt;&lt; endl;       // prints 0
    }
</pre>
    </ul>
    The STL containers usually define members producing iterators (i.e., type
<a name="an2279"></a>
<code>iterator</code>) using member functions <a name="an2280"></a>
<code>begin()</code> and <a name="an2281"></a>
<code>end()</code> and, in the
case of reversed iterators (type <code>reverse_iterator</code>), <a name="an2282"></a>
<code>rbegin()</code> and
<a name="an2283"></a>
<code>rend()</code>. Standard practice requires the iterator range to be <em>left
inclusive</em>: the notation <a name="an2284"></a>
<code>[left, right)</code> indicates that <code>left</code> is an
iterator pointing to the first element that is to be considered, while
<code>right</code> is an iterator pointing just <em>beyond</em> the last element to be
used. The iterator-range is said to be <a name="an2285"></a>
<em>empty</em> when <code>left == right</code>.
Note that with <a name="an2286"></a>
empty containers <a name="an2287"></a>
 the begin- and
end-iterators are equal to each other.
<p>
The following example shows a situation where all elements of a vector of
strings are written to <code>cout</code> using the iterator range
<code>[begin(), end())</code>, and the iterator range <code>[rbegin(),
rend())</code>. Note that the <code>for-loops</code> for both ranges are identical:
    <pre>
    #include &lt;iostream&gt;
    #include &lt;vector&gt;
    #include &lt;string&gt;
    using namespace std;

    int main(int argc, char **argv)
    {
        vector&lt;string&gt; args(argv, argv + argc);

        for
        (
            vector&lt;string&gt;::iterator iter = args.begin();
                iter != args.end();
                    ++iter
        )
            cout &lt;&lt; *iter &lt;&lt; " ";
        cout &lt;&lt; endl;

        for
        (
            vector&lt;string&gt;::reverse_iterator iter = args.rbegin();
                iter != args.rend();
                    ++iter
        )
            cout &lt;&lt; *iter &lt;&lt; " ";
        cout &lt;&lt; endl;

        return 0;
    }
</pre>
<p>
Furthermore, the STL defines <em>const_iterator</em> types to be able to visit
a series of elements in a constant container. Whereas the elements of the
vector in the previous example could have been altered, the elements of the
vector in the next example are immutable, and <code>const_iterator</code>s are
required:
        <pre>
    #include &lt;iostream&gt;
    #include &lt;vector&gt;
    #include &lt;string&gt;
    using namespace std;

    int main(int argc, char **argv)
    {
        vector&lt;string&gt; const args(argv, argv + argc);

        for
        (
            vector&lt;string&gt;::const_iterator iter = args.begin();
                iter != args.end();
                    ++iter
        )
            cout &lt;&lt; *iter &lt;&lt; " ";
        cout &lt;&lt; endl;

        for
        (
            vector&lt;string&gt;::const_reverse_iterator iter = args.rbegin();
                iter != args.rend();
                    ++iter
        )
            cout &lt;&lt; *iter &lt;&lt; " ";
        cout &lt;&lt; endl;

        return 0;
    }
</pre>
    The examples also illustrates that plain <a name="an2288"></a>

        <a name="an2289"></a>
 pointers can be used instead of
iterators. The initialization <code>vector&lt;string&gt; args(argv, argv + argc)</code>
provides the <code>args</code> vector with a pair of pointer-based iterators: <code>argv</code>
points to the first element to initialize <code>sarg</code> with, <code>argv + argc</code>
points just beyond the last element to be used, <code>argv++</code> reaches the next
string. This is a general characteristic of pointers, which is why they too
can be used in situations where <code>iterators</code> are expected.
<p>
The STL defines five <a name="an2290"></a>
types of iterators. These types recur in the
generic algorithms, and in order to be able to create a particular type of
iterator yourself it is <a name="an2291"></a>
 important to know their
characteristics. In general, iterators must define:
    <ul>
    <li><a name="an2292"></a>
<code>operator==()</code>, testing two iterators for equality,
    <li><a name="an2293"></a>
<code>operator++()</code>, incrementing the iterator, as <a name="an2294"></a>
prefix operator,
    <li><a name="an2295"></a>
<code>operator*()</code>, to access the element the iterator refers to,
    </ul>
    The following types of iterators are used when describing generic
algorithms later in this chapter:
    <ul>
    <li> <a name="an2296"></a>
<strong>InputIterators</strong>.
        <blockquote>InputIterators can <a name="an2297"></a>
read from a container.  The dereference
operator is guaranteed to work as <a name="an2298"></a>
<code>rvalue</code> in expressions. Instead of an
InputIterator it is also possible to (see below) use a Forward-,
Bidirectional- or RandomAccessIterator. With the generic algorithms presented
in this chapter. Notations like <a name="an2299"></a>
<code>InputIterator1</code> and <a name="an2300"></a>
<code>InputIterator2</code>
may be observed as well. In these cases, numbers are used to indicate which
iterators `belong together'. E.g., the generic function <code>inner_product()</code>
has the following prototype:
        <pre>
    Type inner_product(InputIterator1 first1, InputIterator1 last1,
                   InputIterator2 first2, Type init);
</pre>
    Here <code>InputIterator1 first1</code> and <code>InputIterator1 last1</code> are a set of
input iterators defining one range, while <code>InputIterator2 first2</code> defines
the beginning of a second range. Analogous notations like these may be
observed with other iterator types.</blockquote>
    <li> <a name="an2301"></a>
<strong>OutputIterators</strong>:
        <blockquote>OutputIterators can be used to
    <a name="an2302"></a>
write to a container. The dereference operator is guaranteed to work as
an <a name="an2303"></a>
<code>lvalue</code> in expressions, but not necessarily as <code>rvalue</code>. Instead of an
OutputIterator it is also possible to use, see below, a Forward-,
Bidirectional- or RandomAccessIterator.</blockquote>
    <li> <a name="an2304"></a>
<strong>ForwardIterators</strong>:
        <blockquote>ForwardIterators combine InputIterators and
OutputIterators. They can be used to <a name="an2305"></a>
traverse containers in one direction,
for reading and/or writing. Instead of a ForwardIterator it is also possible
to use a Bidirectional- or RandomAccessIterator.</blockquote>
    <li> <a name="an2306"></a>
<strong>BidirectionalIterators</strong>:
        <blockquote>BidirectionalIterators can be used to <a name="an2307"></a>
traverse containers in
both directions, for reading and writing. Instead of a BidirectionalIterator
it is also possible to use a RandomAccessIterator. For example, to traverse a
<a name="an2308"></a>
list or a <a name="an2309"></a>
deque a BidirectionalIterator may be useful.</blockquote>
    <li> <a name="an2310"></a>
<strong>RandomAccessIterators</strong>:
        <blockquote>RandomAccessIterators provide <a name="an2311"></a>
random access to container
elements. An algorithm such as <a name="an2312"></a>
<code>sort()</code> requires a RandomAccessIterator, and
can therefore <em>not</em> be used with lists or maps, which only provide
BidirectionalIterators.</blockquote>
    </ul>
    The example given with the RandomAccessIterator illustrates how to
approach <a name="an2313"></a>
 iterators: look for the iterator
that's required by the (generic) algorithm, and then see whether the
datastructure supports the required iterator. If not, the algorithm cannot be
used with the particular datastructure.
<p>
<a name="INSERTER"></a><a name="l235"></a>
<h3>17.2.1: Insert iterators</h3>
    <a name="stl/insertiterators"></a>Generic algorithms often require a target container into which the results of
the algorithm are deposited. For example, the <a href="cplusplus17.html#COPY"><code>copy()</code></a> algorithm
has three parameters, the first two defining the range of visited elements,
and the third parameter defines the first position where the results of the
copy operation should be stored. With the <code>copy()</code> algorithm the number of
elements that are copied are usually available beforehand, since the number is
usually determined using pointer arithmetic. However, there are situations
where pointer arithmetic cannot be used. Analogously, the number of resulting
elements sometimes differs from the number of elements in the initial
range. The generic algorithm <a href="cplusplus17.html#UNIQUECP"><code>unique_copy()</code></a> is a case in
point: the number of elements which are copied to the destination container is
normally not known beforehand.
<p>
In situations like these, an <a name="an2314"></a>
<code>inserter</code> adaptor function may be used to
create elements in the destination container when they are needed.
There are three types of <code>inserter()</code> adaptors:
    <ul>
    <li><a name="an2315"></a>
<code>back_inserter()</code>: calls the container's <a name="an2316"></a>
<code>push_back()</code> member to add
new elements at the end of the container. E.g., to copy all elements of
<code>source</code> in reversed order to the back of <code>destination</code>:
        <pre>
    copy(source.rbegin(), source.rend(), back_inserter(destination));
</pre>
    <li><a name="an2317"></a>
<code>front_inserter()</code> calls the container's <a name="an2318"></a>
<code>push_front()</code> member to add
new elements at the beginning of the container. E.g., to copy all elements of
<code>source</code> to the front of the destination container (thereby also reversing
the order of the elements):
        <pre>
    copy(source.begin(), source.end(), front_inserter(destination));
</pre>
    <li><a name="an2319"></a>
<code>inserter()</code> calls the container's <a name="an2320"></a>
<code>insert()</code> member to add new
elements starting at a specified starting point. E.g., to copy all elements of
<code>source</code> to the destination container, starting at the beginning of
<code>destination</code>, shifting existing elements beyond the newly inserted
elements:
        <pre>
    copy(source.begin(), source.end(), inserter(destination,
        destination.begin()));
</pre>
    </ul>
    Concentrating on the <code>back_inserter()</code>, this iterator expects the name
of a container having a member <code>push_back()</code>. This member is called by the
inserter's <code>operator()()</code> member. When a class (other than the abstract
containers) supports a <code>push_back()</code> container, its objects can also be
used as arguments of the <code>back_inserter()</code> if the class defines a
        <pre>
    typedef DataType const &amp;const_reference;
</pre>
    in its interface, where <code>DataType const &amp;</code> is the type of the parameter
of the class's member function <code>push_back()</code>. For example, the following
program defines a (compilable) skeleton of a class <code>IntStore</code>, whose objects
can be used as arguments of the <code>back_inserter</code> iterator:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iterator&gt;
    using namespace std;

    class Y
    {
        public:
            typedef int const &amp;const_reference;

            void push_back(int const &amp;)
            {}
    };

    int main()
    {
        int arr[] = {1};
        Y y;

        copy(arr, arr + 1, back_inserter(y));
    }
</pre>
<p>
<a name="ISTREAMITERATORS"></a><a name="l236"></a>
<h3>17.2.2: Iterators for `istream' objects</h3>
    <a name="stl/istreamiterators"></a>The <a name="an2321"></a>
<code>istream_iterator&lt;Type&gt;()</code> can be used to define an iterator (pair) for
<a name="an2322"></a>
<code>istream</code> objects. The general form of the <code>istream_iterator&lt;Type&gt;()</code>
iterator is:
        <pre>
    istream_iterator&lt;Type&gt; identifier(istream &amp;inStream)
</pre>
    Here, <code>Type</code> is the type of the data elements that are read from
the <code>istream</code> stream. <code>Type</code> may be any type for which <code>operator</code>>><code>()</code> is
defined with <code>istream</code> objects.
<p>
The <a name="an2323"></a>
default constructor defines the end of the iterator pair,
corresponding to <a name="an2324"></a>
end-of-stream. For example,
        <pre>
    istream_iterator&lt;string&gt; endOfStream;
</pre>
    Note that the actual <em>stream</em> object which was specified for the
begin-iterator is <em>not</em> mentioned here.
<p>
Using a <a href="cplusplus17.html#INSERTER"><code>back_inserter()</code></a> and a set of
<code>istream_iterator&lt;&gt;()</code> adaptors, all strings could be read from <code>cin</code> as
follows:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iterator&gt;
    #include &lt;string&gt;
    #include &lt;vector&gt;
    using namespace std;

    int main()
    {
        vector&lt;string&gt; vs;

        copy(istream_iterator&lt;string&gt;(cin), istream_iterator&lt;string&gt;(),
             back_inserter(vs));

        for
        (
            vector&lt;string&gt;::iterator from = vs.begin();
                from != vs.end();
                    ++from
        )
            cout &lt;&lt; *from &lt;&lt; " ";
        cout &lt;&lt; endl;

        return 0;
    }
</pre>
    In the above example, note the use of the <a name="an2325"></a>
anonymous versions of the
<code>istream_iterator</code> adaptors. Especially note the use of the anonymous
default constructor. The following (non-anonymous) construction could have
been used instead of <code>istream_iterator&lt;string&gt;()</code>:
        <pre>
    istream_iterator&lt;string&gt; eos;

    copy(istream_iterator&lt;string&gt;(cin), eos, back_inserter(vs));
</pre>
    Before <code>istream_iterators</code> can be used the following preprocessor
directive must have been specified: <a name="an2326"></a>

        <pre>
    #include &lt;iterator&gt;
</pre>
    This is implied when <a name="an2327"></a>
<code>iostream</code> is included.
<p>
<a name="l237"></a>
<h3>17.2.3: Iterators for `istreambuf' objects</h3>
    <a name="stl/istreambufiterators"></a>Input iterators are also available for <a name="an2328"></a>
<code>streambuf</code> objects.
Before <a name="an2329"></a>
<code>istreambuf_iterators</code> can be used the following preprocessor
directive must have been specified: <a name="an2330"></a>

        <pre>
    #include &lt;iterator&gt;
</pre>
    The <a name="an2331"></a>
<code>istreambuf_iterator</code> is available for reading from <code>streambuf</code>
objects supporting <a name="an2332"></a>
input operations. The standard operations
that are available for <a name="an2333"></a>
<code>istream_iterator</code> objects are also available
for <code>istreambuf_iterators</code>. There are three <a name="an2334"></a>
 constructors:
    <ul>
    <li><a name="an2335"></a>
<code>istreambuf_iterator&lt;Type&gt;()</code>:<blockquote>This constructor represents the <a name="an2336"></a>
end-of-stream iterator while
extracting values of type <code>Type</code> from the <code>streambuf</code>.</blockquote>
    <li><a name="an2337"></a>
<code>istreambuf_iterator&lt;Type&gt;(istream)</code>:<blockquote>This constructor constructs an <code>istreambuf_iterator</code> accessing
the <code>streambuf</code> of the <a name="an2338"></a>
<code>istream</code> object, used as  the
constructor's argument.</blockquote>
    <li><a name="an2339"></a>
<code>istreambuf_iterator&lt;Type&gt;(streambuf *)</code>:<blockquote>This constructor constructs an <code>istreambuf_iterator</code> accessing
the <code>streambuf</code> whose address is used as the constructor's argument.</blockquote>
    </ul>
    In section <a href="cplusplus17.html#OSTREAMBUFITER">17.2.4.1</a> an example is given using both
<code>istreambuf_iterators</code> and <a name="an2340"></a>
 <code>ostreambuf_iterators</code>.
<p>
<a name="l238"></a>
<h3>17.2.4: Iterators for `ostream' objects</h3>
    <a name="stl/ostreamiterators"></a>The <a name="an2341"></a>
<code>ostream_iterator&lt;Type&gt;()</code> can be used to define a destination iterator
for an <a name="an2342"></a>
<code>ostream</code> object. The general forms
of the <code>ostream_iterator&lt;Type&gt;()</code> iterator are:
        <pre>
    ostream_iterator&lt;Type&gt; identifier(ostream &amp;outStream), // and:
    ostream_iterator&lt;Type&gt; identifier(ostream &amp;outStream, char const *delim);
</pre>
    <code>Type</code> is the type of the data elements that should be written to the
<code>ostream</code> stream. <code>Type</code> may be any type for which <code>operator</code><<<code>()</code> is defined
in combinations with <code>ostream</code> objects.  The latter form of the
<code>ostream_iterators</code> separates the individual <code>Type</code> data elements by
<a name="an2343"></a>
<code>delimiter</code> strings. The former definition does not use any delimiters.
<p>
The following example shows how
<a href="cplusplus17.html#ISTREAMITERATORS"><code>istream_iterators</code></a> and an <code>ostream_iterator</code> may
be used to copy information of a file to another file. A subtlety is the
statement <code>in.unsetf(ios::skipws)</code>: it resets the <a name="an2344"></a>
<code>ios::skipws</code> flag. The
consequence of this is that the default behavior of <code>operator</code>>><code>()</code>, to skip
whitespace, is modified. White space characters are simply returned by the
operator, and the file is copied unrestrictedly. Here is the program:
        <pre>
</pre>
    Before <code>ostream_iterators</code> can be used the following preprocessor
directive must have been specified: <a name="an2345"></a>

        <pre>
    #include &lt;iterator&gt;
</pre>
<p>
<a name="OSTREAMBUFITER"></a><a name="l239"></a>
<strong>17.2.4.1: Iterators for `ostreambuf' objects</strong>
    <a name="stl/ostreambufiterators"></a>Before an <a name="an2346"></a>
<code>ostreambuf_iterator</code>  can be used the following preprocessor
directive must have been specified: <a name="an2347"></a>

        <pre>
    #include &lt;iterator&gt;
</pre>
    The <a name="an2348"></a>
<code>ostreambuf_iterator</code> is available for writing to <code>streambuf</code>
objects supporting <a name="an2349"></a>
output operations. The standard operations
that are  available for <a name="an2350"></a>
<code>ostream_iterator</code> objects are also available
for <code>ostreambuf_iterators</code>. There are two <a name="an2351"></a>

constructors:
    <ul>
    <li><a name="an2352"></a>
<code>ostreambuf_iterator&lt;Type&gt;(ostream)</code>:<blockquote>This constructor constructs an <code>ostreambuf_iterator</code> accessing
the <code>streambuf</code> of the <a name="an2353"></a>
<code>ostream</code> object, used as the
constructor's argument, to insert values of type <code>Type</code>.</blockquote>
    <li><a name="an2354"></a>
<code>ostreambuf_iterator&lt;Type&gt;(streambuf *)</code>:<blockquote>This constructor constructs an <code>ostreambuf_iterator</code> accessing
the <code>streambuf</code> whose address is used as the constructor's argument.</blockquote>
    </ul>
    Here is an example using both <a name="an2355"></a>

<code>istreambuf_iterators</code> and an <code>ostreambuf_iterator</code>, showing yet another
way to copy a stream:
        <pre>
    #include &lt;iostream&gt;
    #include &lt;algorithm&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        istreambuf_iterator&lt;char&gt; in(cin.rdbuf());
        istreambuf_iterator&lt;char&gt; eof;
        ostreambuf_iterator&lt;char&gt; out(cout.rdbuf());

        copy(in, eof, out);

        return 0;
    }
</pre>
<p>
<a name="AUTOPTR"></a><a name="l240"></a>
<h2>17.3: The class 'auto_ptr'</h2>
<a name="stl/autoptr"></a>One of the problems using pointers is that strict <a name="an2356"></a>
bookkeeping is required
about their memory use and lifetime. When a pointer variable goes
    <a name="an2357"></a>
out of scope, the memory pointed to by the pointer is suddenly
inaccessible, and the program suffers from a <a name="an2358"></a>
memory leak. For example, in
the following function <code>fun()</code>, a memory leak is created by calling
<code>fun()</code>: the allocated <code>int</code> value remains inaccessibly allocated:
        <pre>
    void fun()
    {
        new int;
    }
</pre>
    To prevent memory leaks strict bookkeeping is required: the programmer has
to make sure that the memory pointed to by a pointer is deleted just before
the pointer variable goes <a name="an2359"></a>
out of scope. In the above example the repair
would be:
        <pre>
    void fun()
    {
        delete new int;
    }
</pre>
    Now <code>fun()</code> only wastes a bit of time.
<p>
When a pointer variable points to <em>a single value or object</em>, the
bookkeeping requirements may be relaxed when the pointer variable is defined
as a <code>std::auto_ptr</code> <a name="an2360"></a>
 object. Auto_ptrs are <em>objects</em>,
masquerading as pointers. Since they're objects, their destructors are called
when they go out of scope, and because of that, their destructors will take
the responsibility of deleting the dynamically allocated memory.
<p>
Before <code>auto_ptrs</code> can be used the following preprocessor directive must
have been specified: <a name="an2361"></a>

        <pre>
    #include &lt;memory&gt;
</pre>
    Normally, an <code>auto_ptr</code> object is initialized using a dynamically
created value or object.
<p>
The following <em>restrictions</em> <a name="an2362"></a>
 apply to
<code>auto_ptrs</code>:
    <ul>
    <li> the <code>auto_ptr</code> object cannot be used to point to
        <a name="an2363"></a>
arrays of objects.
    <li> an <code>auto_ptr</code> object should only point to memory that was made
available dynamically, as only <a name="an2364"></a>
dynamically allocated memory can be deleted.
    <li> multiple <code>auto_ptr</code> objects should not be allowed to point to the
same block of dynamically allocated memory. The <code>auto_ptr</code>'s interface was
designed to prevent this from happening. Once an <code>auto_ptr</code> object goes out
of scope, it deletes the memory it points to, immediately changing any other
object also pointing to the allocated memory into a <a name="an2365"></a>
 wild
pointer.
    </ul>
    The <code>class auto_ptr</code> defines several member functions
to access the pointer itself or to have the <code>auto_ptr</code> point to another
block of memory. These member functions and ways to construct <code>auto_ptr</code>
objects are discussed in the next sections.
<p>
<a name="l241"></a>
<h3>17.3.1: Defining `auto_ptr' variables</h3>
    <a name="stl/defining"></a>There are three ways to <a name="an2366"></a>
 define <code>auto_ptr</code>
objects. Each definition contains the usual <code>&lt;type&gt;</code> specifier between
angle brackets. Concrete examples are given in the coming sections, but an
overview of the various possibilities is presented here:
    <ul>
    <li> The basic form initializes an <code>auto_ptr</code> object to point to a block
of memory allocated by the <code>new</code> operator:
        <pre>
    auto_ptr&lt;type&gt; identifier (new-expression);
</pre>
    This form is discussed in section <a href="cplusplus17.html#AUTONEW">17.3.2</a>.
    <li> Another form initializes an <code>auto_ptr</code> object using a copy
constructor:
        <pre>
    auto_ptr&lt;type&gt; identifier(another auto_ptr for type);
</pre>
    This form is discussed in section <a href="cplusplus17.html#AUTOOTHER">17.3.3</a>.
    <li> The third form simply creates an <code>auto_ptr</code> object that
does not point to a particular block of memory:
        <pre>
    auto_ptr&lt;type&gt; identifier;
</pre>
    This form is discussed in section <a href="cplusplus17.html#AUTOPLAIN">17.3.4</a>.
    </ul>
<p>
<a name="AUTONEW"></a><a name="l242"></a>
<h3>17.3.2: Pointing to a newly allocated object</h3>
    <a name="stl/autonew"></a>The basic form to <a name="an2367"></a>
 initialize an <code>auto_ptr</code>
object is to provide its constructor with a block of memory allocated
by <a name="an2368"></a>
<code>operator new</code> operator. The generic form is:
        <pre>
    auto_ptr&lt;type&gt; identifier(new-expression);
</pre>
    For example, to initialize an <code>auto_ptr</code> to point to
a <code>string</code> object  the
following construction can be used:
        <pre>
    auto_ptr&lt;string&gt; strPtr(new string("Hello world"));
</pre>
    To initialize an <code>auto_ptr</code> to point to a <code>double</code> value the
following construction can be used:
        <pre>
    auto_ptr&lt;double&gt; dPtr(new double(123.456));
</pre>
    Note the use of <code>operator new</code> in the above expressions. Using <code>new</code>
ensures the dynamic nature of the memory pointed to by the <code>auto_ptr</code>
objects and allows the deletion of the memory once <code>auto_ptr</code> objects go
<a name="an2369"></a>
out of scope. Also note that the <code>type</code> does <em>not</em> contain the pointer:
the <a name="an2370"></a>
 <code>type</code> used in the <code>auto_ptr</code> construction is
the same as used in the <code>new</code> expression.
<p>
In the example allocating an <code>int</code> values given in section <a href="cplusplus17.html#AUTOPTR">17.3</a>,
the memory leak can be avoided using an <code>auto_ptr</code> object:
        <pre>
    #include &lt;memory&gt;
    using namespace std;

    void fun()
    {
        auto_ptr&lt;int&gt; ip(new int);
    }
</pre>
    All <a name="an2371"></a>
 member functions  available for
objects allocated by the <code>new</code> expression can be reached via the
<code>auto_ptr</code> as if it was a plain pointer to the dynamically allocated
object. For example, in the following program the text `<code>C++</code>' is inserted
behind the word `<code>hello</code>':
        <pre>
    #include &lt;iostream&gt;
    #include &lt;memory&gt;
    using namespace std;

    int main()
    {
        auto_ptr&lt;string&gt; sp(new string("Hello world"));

        cout &lt;&lt; *sp &lt;&lt; endl;

        sp-&gt;insert(strlen("Hello "), "C++ ");
        cout &lt;&lt; *sp &lt;&lt; endl;
    }
    /*
        produced output:

        Hello world
        Hello C++ world
    */
</pre>
<p>
<a name="AUTOOTHER"></a><a name="l243"></a>
<h3>17.3.3: Pointing to another `auto_ptr'</h3>
    <a name="stl/autoother"></a>    An <code>auto_ptr</code> <a name="an2372"></a>
 may also be initialized
by another <code>auto_ptr</code> object for the same type.
The generic form is:
        <pre>
    auto_ptr&lt;type&gt; identifier(other auto_ptr object);
</pre>
    For example, to initialize an <code>auto_ptr&lt;string&gt;</code>, given the variable
<code>sp</code> defined in the previous section, the following construction can be
used:
        <pre>
    auto_ptr&lt;string&gt; strPtr(sp);
</pre>
    Analogously, the assignment operator can
<a name="an2373"></a>
 be used. An <code>auto_ptr</code> object may be assigned
to another <code>auto_ptr</code> object of the same type. For example:
        <pre>
    #include &lt;iostream&gt;
    #include &lt;memory&gt;
    #include &lt;string&gt;
    using namespace std;

    int main()
    {
        auto_ptr&lt;string&gt; hello1(new string("Hello world"));
        auto_ptr&lt;string&gt; hello2(hello1);
        auto_ptr&lt;string&gt; hello3;

        hello3 = hello2;
        cout &lt;&lt; *hello1 &lt;&lt; endl &lt;&lt;
                *hello2 &lt;&lt; endl &lt;&lt;
                *hello3 &lt;&lt; endl;
    }
    /*
        Produced output:

        Segmentation fault
    */
</pre>
    Looking at the above example, we see that
    <ul>
    <li> <code>hello1</code> is initialized as described in the previous section.
    <li> Next <code>hello2</code> is defined, and it receives its value from
<code>hello1</code>, using a <a name="an2374"></a>
copy constructor type of initialization. This
effectively changes <code>hello1</code> into a 0-pointer.
    <li> Then <code>hello3</code> is defined as a default <code>auto_ptr&lt;string&gt;</code>, but it
receives its value through an assignment from <code>hello2</code>, which then becomes a
0-pointer too.
    </ul>
    The program generates a <a name="an2375"></a>
<em>segmentation fault</em>. The reason
for this will now be clear: it is caused by dereferencing 0-pointers. At the
end, only <code>hello3</code> actually points to a <code>string</code>.
<p>
<a name="AUTOPLAIN"></a><a name="l244"></a>
<h3>17.3.4: Creating a plain `auto_ptr'</h3>
    <a name="stl/autoplain"></a>We've already seen the third <a name="an2376"></a>
 form to create an
<code>auto_ptr</code> object: Without arguments an empty <code>auto_ptr</code> object is
constructed not pointing to a particular block of memory:
        <pre>
    auto_ptr&lt;type&gt; identifier;
</pre>
    In this case the <a name="an2377"></a>
 underlying pointer is set to
<code>0</code> (zero). Since the <code>auto_ptr</code> object itself is not the pointer, its
value cannot be compared to <code>0</code> to see if it has not been initialized. E.g.,
code like
        <pre>
    auto_ptr&lt;int&gt; ip;

    if (!ip)
        cout &lt;&lt; "0-pointer with an auto_ptr object ?" &lt;&lt; endl;
</pre>
    will not produce any output (actually, it won't compile either...). So,
how do we inspect the value of the pointer that's maintained by the
<code>auto_ptr</code> object? For this the member <a name="an2378"></a>
 <code>get()</code> is
available. This member function, as well as the other member functions of the
class <code>auto_ptr</code> are described in the next section.
<p>
<a name="l245"></a>
<h3>17.3.5: Operators and members</h3>
    <a name="stl/autoptrmembers"></a>The following <a name="an2379"></a>
 operators are defined for the class
<code>auto_ptr</code>:
    <ul>
    <li><a name="an2380"></a>
<code>auto_ptr &amp;auto_ptr&lt;Type&gt;operator=(auto_ptr&lt;Type&gt; &amp;other)</code>:<blockquote>This operator will transfer the memory pointed to by the <a name="an2381"></a>
rvalue
<code>auto_ptr</code> object to the <a name="an2382"></a>
lvalue <code>auto_ptr</code> object. So, the rvalue
object <em>loses</em> the memory it pointed at, and turns into a 0-pointer.</blockquote>
    <li><a name="an2383"></a>
<code>Type &amp;auto_ptr&lt;Type&gt;operator*()</code>:<blockquote>This operator returns a reference to
the information stored in the <code>auto_ptr</code> object. It acts like a normal
pointer <a name="an2384"></a>
dereference operator.</blockquote>
    <li><a name="an2385"></a>
<code>Type *auto_ptr&lt;Type&gt;operator-&gt;()</code>:<blockquote>This operator returns a pointer to
the information stored in the <code>auto_ptr</code> object. Through this operator
members of a stored object an be selected. For example:
            <pre>
    auto_ptr&lt;string&gt; sp(new string("hello"));

    cout &lt;&lt; sp-&gt;c_str() &lt;&lt; endl;
</pre>
        </blockquote>
    </ul>
    The following <a name="an2386"></a>
member functions are defined for <code>auto_ptr</code> objects:
    <ul>
    <li><a name="an2387"></a>
<code>Type *auto_ptr&lt;Type&gt;::get()</code>:<blockquote>This operator does
the same as <code>operator-&gt;()</code>: it returns a pointer to the information stored
in the <code>auto_ptr</code> object. This pointer can be inspected: if it's zero the
<code>auto_ptr</code> object does not point to any memory.  This member cannot be used
to let the <code>auto_ptr</code> object point to (another) block of memory.</blockquote>
    <li><a name="an2388"></a>
<code>Type *auto_ptr&lt;Type&gt;::release()</code>:<blockquote>This operator returns a pointer to the information stored in the
<code>auto_ptr</code> object, which loses the memory it pointed at (and changes into a
<a name="an2389"></a>
0-pointer). The member can be used to transfer the information stored in
the <code>auto_ptr</code> object to a plain <code>Type</code> pointer.  It is the
<a name="an2390"></a>
responsibility of the programmer to <a name="an2391"></a>
delete the memory returned by this
member function.</blockquote>
    <li><a name="an2392"></a>
<code>void auto_ptr&lt;Type&gt;::reset(Type *)</code>:<blockquote>This operator may also be called <em>without</em> argument, to delete the
memory stored in the <code>auto_ptr</code> object, or with a pointer to a
<a name="an2393"></a>
dynamically allocated block of memory, which will thereupon be the
memory accessed by the <code>auto_ptr</code> object. This member function can
be used to assign a new <a name="an2394"></a>
 block of
memory (new content) to an <code>auto_ptr</code> object.</blockquote>
    </ul>
<p>
<a name="AUTOCONS"></a><a name="l246"></a>
<h3>17.3.6: Constructors and pointer data members</h3>
    <a name="stl/autoptrconstructors"></a>    Now that the <code>auto_ptr</code>'s main features have been described, consider
the following simple class:
        <pre>
    // required #includes

    class Map
    {
        std::map&lt;string, Data&gt; *d_map;
        public:
            Map(char const *filename) throw(std::exception);
    };
</pre>
    The class's constructor <code>Map()</code> performs the following tasks:
    <ul>
    <li> It allocates a <code>std::map</code> object;
    <li> It opens the file whose name is given as the constructor's argument;
    <li> It reads the file, thereby filling the map.
    </ul>
    Of course, it may not be possible to open the file.  In that case an
appropriate exception is thrown. So, the constructor's implementation will
look somewhat like this:
        <pre>
    Map::Map(char const *fname)
    :
        d_map(new std::map&lt;std::string, Data&gt;) throw(std::exception)
    {
        ifstream istr(fname);
        if (!istr)
            throw std::exception("can't open the file");
        fillMap(istr);
    }
</pre>
    What's wrong with this implementation? Its main weakness is that it hosts
a potential <a name="an2395"></a>
memory leak. The memory leak only occurs when the exception is
actually thrown. In all other cases, the function operates perfectly
well. When the exception is thrown, the map has just been dynamically
allocated. However, even though the class's destructor will dutifully call
<code>delete d_map</code>, the destructor is actually never called, as the destructor
    <a name="an2396"></a>
 will only be called to destroy
objects that were constructed completely. Since the constructor terminates in
an exception, its associated object is not constructed completely, and
therefore that object's destructor is never called.
<p>
<code>Auto_ptrs</code> may be used to prevent these kinds of problems. By defining
<code>d_map</code> as
        <pre>
        std::auto_ptr&lt;std::map&lt;std::string, Data&gt; &gt;
</pre>
    it suddenly changes into an object. Now, <code>Map</code>'s constructor may safely
throw an exception. As <code>d_map</code> is an object itself, its destructor will be
called by the time the (however incompletely constructed) <code>Map</code> object goes
out of scope.
<p>
As a <a name="an2397"></a>
rule of thumb: classes should use <code>auto_ptr</code> objects, rather
than plain pointers for their pointer data members if there's any chance that
their constructors will end prematurely in an exception.
<p>
<a name="l247"></a>
<h2>17.4: The Generic Algorithms</h2>
<a name="stl/generic"></a>The following sections describe the <a name="an2398"></a>
generic algorithms in alphabetical
order. For each algorithm the following information is provided:
    <ul>
    <li> The required header file;
    <li> The function prototype;
    <li> A short description;
    <li> A short example.
    </ul>
    In the <a name="an2399"></a>
prototypes of the algorithms <code>Type</code> is used to specify a
<a name="an2400"></a>
generic data type. Also, the particular type of iterator (see section
<a href="cplusplus17.html#ITERATORS">17.2</a>) that is required is mentioned, as well as other generic types
that might be required (e.g., performing <code>BinaryOperations</code>, like
<code>plus&lt;Type&gt;()</code>).
<p>
Almost every generic algorithm expects an iterator range <a name="an2401"></a>
<code>[first, last)</code>,
defining the range of elements on which the algorithm operates. The iterators
point to objects or values. When an iterator points to a <code>Type</code> value or
object, function objects used by the algorithms usually receive <code>Type const
&amp;</code> objects or values: function objects can therefore not modify the objects
they receive as their arguments. This does not hold true for
    <a name="an2402"></a>
<em>modifying generic algorithms</em>, which <em>are</em> (of course) able to
modify the objects they operate upon.
<p>
Generic algorithms may be categorized. In the <strong>C++</strong> Annotations the
following <a name="an2403"></a>
categories of generic algorithms are distinguished:
    <ul>
    <li> Comparators: comparing (ranges of) elements:
        <blockquote>
            Requires: <a name="an2404"></a>
<code>#include &lt;algorithm&gt;</code>
<p>
<a href="cplusplus17.html#EQUAL">equal()</a>;
            <a href="cplusplus17.html#INCLUDES">includes()</a>;
            <a href="cplusplus17.html#LEXCOMP">lexicographical_compare()</a>;
            <a href="cplusplus17.html#MAX">max()</a>;
            <a href="cplusplus17.html#MIN">min()</a>;
            <a href="cplusplus17.html#MISMATCH">mismatch()</a>;
        </blockquote>
    <li> Copiers: performing copy operations:
        <blockquote>
            Requires: <a name="an2405"></a>
<code>#include &lt;algorithm&gt;</code>
<p>
<a href="cplusplus17.html#COPY">copy()</a>;
            <a href="cplusplus17.html#COPYBACK">copy_backward()</a>;
            <a href="cplusplus17.html#PARTSORTCP">partial_sort_copy()</a>;
            <a href="cplusplus17.html#REMOVECP">remove_copy()</a>;
            <a href="cplusplus17.html#REMOVECPIF">remove_copy_if()</a>;
            <a href="cplusplus17.html#REPLACECP">replace_copy()</a>;
            <a href="cplusplus17.html#REPLACEIF">replace_copy_if()</a>;
            <a href="cplusplus17.html#REVERSECP">reverse_copy()</a>;
            <a href="cplusplus17.html#ROTATECP">rotate_copy()</a>;
            <a href="cplusplus17.html#UNIQUECP">unique_copy()</a>;
        </blockquote>
    <li> Counters: performing count operations:
        <blockquote>
            Requires: <a name="an2406"></a>
<code>#include &lt;algorithm&gt;</code>
<p>
<a href="cplusplus17.html#COUNT">count()</a>;
            <a href="cplusplus17.html#COUNTIF">count_if()</a>;
        </blockquote>
    <li> Heap operators: manipulating a <a name="an2407"></a>
max-heap:
        <blockquote>
            Requires: <a name="an2408"></a>
<code>#include &lt;algorithm&gt;</code>
<p>
<a href="cplusplus17.html#MAKEHEAP">make_heap()</a>;
            <a href="cplusplus17.html#POPHEAP">pop_heap()</a>;
            <a href="cplusplus17.html#PUSHHEAP">push_heap()</a>;
            <a href="cplusplus17.html#SORTHEAP">sort_heap()</a>;
        </blockquote>
    <li> Initializers: initializing data:
        <blockquote>
            Requires: <a name="an2409"></a>
<code>#include &lt;algorithm&gt;</code>
<p>
<a href="cplusplus17.html#FILL">fill()</a>;
            <a href="cplusplus17.html#FILLN">fill_n()</a>;
            <a href="cplusplus17.html#GEN">generate()</a>;
            <a href="cplusplus17.html#GENN">generate_n()</a>;
        </blockquote>
    <li> Operators: performing arithmetic operations of some sort:
        <blockquote>
            Requires: <a name="an2410"></a>
<code>#include &lt;numeric&gt;</code>
<p>
<a href="cplusplus17.html#ACCU">accumulate()</a>;
            <a href="cplusplus17.html#ADJDIFF">adjacent_difference()</a>;
            <a href="cplusplus17.html#INNERPROD">inner_product()</a>;
            <a href="cplusplus17.html#PARTSUM">partial_sum()</a>;
        </blockquote>
    <li> Searchers: performing search (and find) operations:
        <blockquote>
            Requires: <a name="an2411"></a>
<code>#include &lt;algorithm&gt;</code>
<p>
<a href="cplusplus17.html#ADJFIND">adjacent_find()</a>;
            <a href="cplusplus17.html#BINSRCH">binary_search()</a>;
            <a href="cplusplus17.html#EQUALRANGE">equal_range()</a>;
            <a href="cplusplus17.html#FIND">find()</a>;
            <a href="cplusplus17.html#FINDEND">find_end()</a>;
            <a href="cplusplus17.html#FINDFIRST">find_first_of()</a>;
            <a href="cplusplus17.html#FINDIF">find_if()</a>;
            <a href="cplusplus17.html#LOWERBOUND">lower_bound()</a>;
            <a href="cplusplus17.html#MAXEL">max_element()</a>;
            <a href="cplusplus17.html#MINEL">min_element()</a>;
            <a href="cplusplus17.html#SEARCH">search()</a>;
            <a href="cplusplus17.html#SEARCHN">search_n()</a>;
            <a href="cplusplus17.html#SETDIF">set_difference()</a>;
            <a href="cplusplus17.html#SETINT">set_intersection()</a>;
            <a href="cplusplus17.html#SETSYM">set_symmetric_difference()</a>;
            <a href="cplusplus17.html#SETUNI">set_union()</a>;
            <a href="cplusplus17.html#UPPERBOUND">upper_bound()</a>;
        </blockquote>
    <li> Shufflers: performing reordering operations (<a name="an2412"></a>
sorting,
            <a name="an2413"></a>
merging, <a name="an2414"></a>
permuting, <a name="an2415"></a>
shuffling, <a name="an2416"></a>
swapping):
        <blockquote>
            Requires: <a name="an2417"></a>
<code>#include &lt;algorithm&gt;</code>
<p>
<a href="cplusplus17.html#INMERGE">inplace_merge()</a>;
            <a href="cplusplus17.html#ITERSWAP">iter_swap()</a>;
            <a href="cplusplus17.html#MERGE">merge()</a>;
            <a href="cplusplus17.html#NEXTPERM">next_permutation()</a>;
            <a href="cplusplus17.html#NTHEL">nth_element()</a>;
            <a href="cplusplus17.html#PARTSORT">partial_sort()</a>;
            <a href="cplusplus17.html#PARTSORTCP">partial_sort_copy()</a>;
            <a href="cplusplus17.html#PARTIT">partition()</a>;
            <a href="cplusplus17.html#PREVPERM">prev_permutation()</a>;
            <a href="cplusplus17.html#SHUFFLE">random_shuffle()</a>;
            <a href="cplusplus17.html#REMOVE">remove()</a>;
            <a href="cplusplus17.html#REMOVECP">remove_copy()</a>;
            <a href="cplusplus17.html#REMOVECPIF">remove_copy_if()</a>;
            <a href="cplusplus17.html#REMOVEIF">remove_if()</a>;
            <a href="cplusplus17.html#REVERSE">reverse()</a>;
            <a href="cplusplus17.html#REVERSECP">reverse_copy()</a>;
            <a href="cplusplus17.html#ROTATE">rotate()</a>;
            <a href="cplusplus17.html#ROTATECP">rotate_copy()</a>;
            <a href="cplusplus17.html#SORT">sort()</a>;
            <a href="cplusplus17.html#STABPART">stable_partition()</a>;
            <a href="cplusplus17.html#STABSORT">stable_sort()</a>;
            <a href="cplusplus17.html#SWAP">swap()</a>;
            <a href="cplusplus17.html#UNIQUE">unique()</a>;
        </blockquote>
    <li> Visitors: visiting elements in a range:
        <blockquote>
            Requires: <a name="an2418"></a>
<code>#include &lt;algorithm&gt;</code>
<p>
<a href="cplusplus17.html#FOREACH">for_each()</a>;
            <a href="cplusplus17.html#REPLACE">replace()</a>;
            <a href="cplusplus17.html#REPLACECP">replace_copy()</a>;
            <a href="cplusplus17.html#REPLACEIF">replace_copy_if()</a>;
            <a href="cplusplus17.html#REPLACEIF">replace_if()</a>;
            <a href="cplusplus17.html#TRANSFORM">transform()</a>;
            <a href="cplusplus17.html#UNIQUECP">unique_copy()</a>;
        </blockquote>
    </ul>
<p>
<a name="ACCU"></a><a name="l248"></a>
<h3>17.4.1: accumulate()</h3>
    <a name="stl/accumulate"></a>    <a name="an2419"></a>

    <ul>
    <li> Header file:
    <pre>
        #include &lt;numeric&gt;
</pre>
    <li> Function prototypes:
        <ul>
        <li><code>Type accumulate(InputIterator first, InputIterator last,
            Type init);</code>
        <li> <code>Type accumulate(InputIterator first, InputIterator
            last, Type init,</code><code>BinaryOperation op);</code>
        </ul>
    <li> Description:
        <ul>
        <li> The first prototype: <a name="an2420"></a>
<code>operator+()</code> is applied to all
elements implied by the iterator range and to the initial value <code>init</code>.
The resulting value is returned.
        <li> The second prototype: the binary operator <code>op()</code> is applied to
all elements implied by the iterator range and to the initial value <code>init</code>,
and the resulting value is returned.
        </ul>
        <li> Example:
        <pre>
    #include &lt;numeric&gt;
    #include &lt;vector&gt;
    #include &lt;iostream&gt;
    using namespace std;

    int main()
    {
        int         ia[] = {1, 2, 3, 4};
        vector&lt;int&gt; iv(ia, ia + 4);

        cout &lt;&lt;
            "Sum of values: " &lt;&lt; accumulate(iv.begin(), iv.end(), int()) &lt;&lt;
            endl &lt;&lt;
            "Product of values: " &lt;&lt; accumulate(iv.begin(), iv.end(), int(1),
                                            multiplies&lt;int&gt;()) &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        Sum of values: 10
        Product of values: 24
    */
</pre>
    </ul>
<p>
<a name="ADJDIFF"></a><a name="l249"></a>
<h3>17.4.2: adjacent_difference()</h3>
    <a name="stl/adjacentdifference"></a>    <a name="an2421"></a>

    <ul>
    <li> Header file:
    <pre>
        #include &lt;numeric&gt;
</pre>
    <li> Function prototypes:
        <ul>
        <li><code>OutputIterator adjacent_difference(InputIterator first,</code>
<code>InputIterator last, OutputIterator result);</code>
        <li><code>OutputIterator adjacent_difference(InputIterator first,</code>
 <code>InputIterator last, OutputIterator result, BinaryOperation
op);</code>
        </ul>
        <li> Description:
            All operations are performed on the original values, all computed
values are returned values.
            <ul>
            <li> The first prototype: the first returned element is equal to
the first element of the input range. The remaining returned elements are
equal to the difference of the corresponding element in the input range and
its previous element.
            <li> The second prototype: the first returned element is equal to
    the first element of the input range. The remaining returned elements are
equal to the result of the binary operator <code>op</code> applied to the
corresponding element in the input range (left operand) and its previous
element (right operand).
        </ul>
        <li> Example:
        <pre>
    #include &lt;numeric&gt;
    #include &lt;vector&gt;
    #include &lt;iostream&gt;
    using namespace std;

    int main()
    {
        int             ia[] = {1, 2, 5, 10};
        vector&lt;int&gt;     iv(ia, ia + 4);
        vector&lt;int&gt;     ov(iv.size());

        adjacent_difference(iv.begin(), iv.end(), ov.begin());

        copy(ov.begin(), ov.end(), ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        adjacent_difference(iv.begin(), iv.end(), ov.begin(), minus&lt;int&gt;());

        copy(ov.begin(), ov.end(), ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        generated output:

        1 1 3 5
        1 1 3 5
    */
</pre>
    </ul>
<p>
<a name="ADJFIND"></a><a name="l250"></a>
<h3>17.4.3: adjacent_find()</h3>
    <a name="stl/adjacentfind"></a>    <a name="an2422"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>ForwardIterator adjacent_find(ForwardIterator first,
ForwardIterator last);</code>
            <li><code>OutputIterator adjacent_find(ForwardIterator first,
ForwardIterator last,</code><code>Predicate pred);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the iterator pointing to the first
element of the first pair of two adjacent equal elements is returned. If no
such element exists, <code>last</code> is returned.
            <li> The second prototype: the iterator pointing to the first
element of the first pair of two adjacent elements for which the binary
predicate <code>pred</code> returns <code>true</code> is returned. If no such element exists,
<code>last</code> is returned.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;string&gt;
    #include &lt;iostream&gt;

    class SquaresDiff
    {
        size_t d_minimum;

        public:
            SquaresDiff(size_t minimum)
            :
                d_minimum(minimum)
            {}
            bool operator()(size_t first, size_t second)
            {
                return second * second - first * first  &gt;= d_minimum;
            }
    };

    using namespace std;

    int main()
    {
        string sarr[] =
            {
                "Alpha", "bravo", "charley", "delta", "echo", "echo",
                "foxtrot", "golf"
            };
        string *last = sarr + sizeof(sarr) / sizeof(string);
        string *result = adjacent_find(sarr, last);

        cout &lt;&lt; *result &lt;&lt; endl;
        result = adjacent_find(++result, last);

        cout &lt;&lt; "Second time, starting from the next position:\n" &lt;&lt;
            (
                result == last ?
                    "** No more adjacent equal elements **"
                :
                    "*result"
            ) &lt;&lt; endl;

        size_t iv[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        size_t *ilast = iv + sizeof(iv) / sizeof(size_t);
        size_t *ires = adjacent_find(iv, ilast, SquaresDiff(10));

        cout &lt;&lt;
            "The first numbers for which the squares differ at least 10: "
            &lt;&lt; *ires &lt;&lt; " and " &lt;&lt; *(ires + 1) &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        echo
        Second time, starting from the next position:
        ** No more adjacent equal elements **
        The first numbers for which the squares differ at least 10: 5 and 6
    */
</pre>
    </ul>
<p>
<a name="BINSRCH"></a><a name="l251"></a>
<h3>17.4.4: binary_search()</h3>
    <a name="stl/binarysearch"></a>    <a name="an2423"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>bool binary_search(ForwardIterator first,
ForwardIterator last,</code><code>Type const &amp;value);</code>
            <li><code>bool binary_search(ForwardIterator first,
ForwardIterator last,</code><code>Type const &amp;value, Comparator comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: <code>value</code> is looked up using binary
search in the range of elements implied by the iterator range <code>[first,
last)</code>. The elements in the range must have been sorted by the
<code>Type::operator&lt;()</code> function. <code>True</code> is returned if the element was found,
<code>false</code> otherwise.
            <li> The second prototype: <code>value</code> is looked up using binary
search in the range of elements implied by the iterator range <code>[first,
last)</code>. The elements in the range must have been sorted by the
<code>Comparator</code> function object. <code>True</code> is returned if the element was found,
<code>false</code> otherwise.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;string&gt;
    #include &lt;iostream&gt;
    #include &lt;functional&gt;
    using namespace std;

    int main()
    {
        string sarr[] =
            {
                "alpha", "bravo", "charley", "delta", "echo",
                "foxtrot", "golf", "hotel"
            };
        string *last = sarr + sizeof(sarr) / sizeof(string);
        bool result = binary_search(sarr, last, "foxtrot");

        cout &lt;&lt; (result ? "found " : "didn't find ") &lt;&lt; "foxtrot" &lt;&lt; endl;

        reverse(sarr, last);                // reverse the order of elements
                                            // binary search now fails:
        result = binary_search(sarr, last, "foxtrot");
        cout &lt;&lt; (result ? "found " : "didn't find ") &lt;&lt; "foxtrot" &lt;&lt; endl;
                                            // ok when using appropriate
                                            // comparator:
        result = binary_search(sarr, last, "foxtrot", greater&lt;string&gt;());
        cout &lt;&lt; (result ? "found " : "didn't find ") &lt;&lt; "foxtrot" &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        found foxtrot
        didn't find foxtrot
        found foxtrot
    */
</pre>
    </ul>
<p>
<a name="COPY"></a><a name="l252"></a>
<h3>17.4.5: copy()</h3>
    <a name="stl/copy"></a>    <a name="an2424"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>OutputIterator copy(InputIterator first,
InputIterator last,</code><code>OutputIterator destination);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The range of elements implied by the iterator range
<code>[first, last)</code> is copied to an output range, starting at
<code>destination</code>, using the assignment operator of the underlying data
type. The return value is the OutputIterator pointing just beyond the last
element that was copied to the destination range (so, `last' in the destination
range is returned).
        </ul>
        <li> Example:<br>
    Note the second call to <code>copy()</code>. It uses an <code>ostream_iterator</code> for
<code>string</code> objects. This iterator will write the <code>string</code> values to the
specified <code>ostream</code> (i.e., <code>cout</code>), separating the values by the specified
separation string (i.e., <code>" "</code>).
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;string&gt;
    #include &lt;iostream&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        string sarr[] =
            {
                "alpha", "bravo", "charley", "delta", "echo",
                "foxtrot", "golf", "hotel"
            };
        string  *last = sarr + sizeof(sarr) / sizeof(string);

        copy(sarr + 2, last, sarr); // move all elements two positions left

                                    // copy to cout using an ostream_iterator
                                    // for strings,
        copy(sarr, last, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        charley delta echo foxtrot golf hotel golf hotel
    */
</pre>
        <li> See also:
            <a href="cplusplus17.html#UNIQUECP"><code>unique_copy()</code></a>
    </ul>
<p>
<a name="COPYBACK"></a><a name="l253"></a>
<h3>17.4.6: copy_backward()</h3>
    <a name="stl/copybackward"></a>    <a name="an2425"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>BidirectionalIterator copy_backward(InputIterator
first,</code>  <code>InputIterator last, BidirectionalIterator
last2);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The range of elements implied by the iterator range
<code>[first, last)</code> are copied from the element at position <code>last - 1</code>
until (and including) the element at position <code>first</code> to the element range,
<em>ending</em> at position <code>last2 - 1</code>, using the assignment operator of the
underlying data type. The destination range is therefore <code>[last2 - (last
- first), last2)</code>.
<p>
The return value is the BidirectionalIterator pointing to the last element that
was copied to the destination range (so, `first' in the destination range, pointed to by <code>last2 - (last - first)</code>, is returned).
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;string&gt;
    #include &lt;iostream&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        string sarr[] =
            {
                "alpha", "bravo", "charley", "delta", "echo",
                "foxtrot", "golf", "hotel"
            };
        string *last = sarr + sizeof(sarr) / sizeof(string);

        copy
        (
            copy_backward(sarr + 3, last, last - 3),
            last,
            ostream_iterator&lt;string&gt;(cout, " ")
        );
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        golf hotel foxtrot golf hotel foxtrot golf hotel
    */
</pre>
    </ul>
<p>
<a name="COUNT"></a><a name="l254"></a>
<h3>17.4.7: count()</h3>
    <a name="stl/count"></a>    <a name="an2426"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>size_t count(InputIterator first, InputIterator last, Type
const &amp;value);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The number of times <code>value</code> occurs in the iterator range
<code>[first, last)</code> is returned. To determine whehter <code>value</code> is equal to
an element in the iterator range <code>Type::operator==()</code> is used.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    using namespace std;

    int main()
    {
        int ia[] = {1, 2, 3, 4, 3, 4, 2, 1, 3};

        cout &lt;&lt; "Number of times the value 3 is available: " &lt;&lt;
            count(ia, ia + sizeof(ia) / sizeof(int), 3) &lt;&lt;
            endl;

        return 0;
    }
    /*
        Generated output:

        Number of times the value 3 is available: 3
    */
</pre>
    </ul>
<p>
<a name="COUNTIF"></a><a name="l255"></a>
<h3>17.4.8: count_if()</h3>
    <a name="stl/countif"></a>    <a name="an2427"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>size_t count_if(InputIterator first,
                                       InputIterator last,</code>
                    <code>Predicate predicate);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The number of times <a name="an2428"></a>
unary predicate `<code>predicate</code>'
returns <code>true</code> when applied to the elements implied by the iterator range
<code>[first, last)</code> is returned.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;

    class Odd
    {
        public:
            bool operator()(int value)
            {
                return value &amp; 1;
            }
    };

    using namespace std;

    int main()
    {
        int     ia[] = {1, 2, 3, 4, 3, 4, 2, 1, 3};

        cout &lt;&lt; "The number of odd values in the array is: " &lt;&lt;
            count_if(ia, ia + sizeof(ia) / sizeof(int), Odd()) &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        The number of odd values in the array is: 5
    */
</pre>
    </ul>
<p>
<a name="EQUAL"></a><a name="l256"></a>
<h3>17.4.9: equal()</h3>
    <a name="stl/equal"></a>    <a name="an2429"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>bool equal(InputIterator first, InputIterator
                last, InputIterator</code>
                <code>otherFirst);</code>
            <li><code>bool equal(InputIterator first, InputIterator last,
                InputIterator</code>
                <code>otherFirst, BinaryPredicate pred);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the elements in the range <code>[first,
last)</code> are compared to a range of equal length starting at <code>otherFirst</code>. The
function returns <code>true</code> if the visited elements in both ranges are equal
pairwise. The ranges need not be of equal length, only the elements in the
indicated range are considered (and must be available).
            <li> The second prototype: the elements in the range
<code>[first, last)</code> are compared to a range of equal length starting at
<code>otherFirst</code>. The function returns <code>true</code> if the binary predicate, applied
to all corresponding elements in both ranges returns <code>true</code> for every pair
of corresponding elements.  The ranges need not be of equal length, only the
elements in the indicated range are considered (and must be available).
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;string&gt;
    #include &lt;iostream&gt;

    class CaseString
    {
        public:
            bool operator()(std::string const &amp;first,
                            std::string const &amp;second) const
            {
                return !strcasecmp(first.c_str(), second.c_str());
            }
    };

    using namespace std;

    int main()
    {
        string first[] =
            {
                "Alpha", "bravo", "Charley", "delta", "Echo",
                "foxtrot", "Golf", "hotel"
            };
        string second[] =
            {
                "alpha", "bravo", "charley", "delta", "echo",
                "foxtrot", "golf", "hotel"
            };
        string *last = first + sizeof(first) / sizeof(string);

        cout &lt;&lt; "The elements of `first' and `second' are pairwise " &lt;&lt;
            (equal(first, last, second) ? "equal" : "not equal") &lt;&lt;
            endl &lt;&lt;
            "compared case-insensitively, they are " &lt;&lt;
            (
                equal(first, last, second, CaseString()) ?
                    "equal" : "not equal"
            ) &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        The elements of `first' and `second' are pairwise not equal
        compared case-insensitively, they are equal
    */
</pre>
    </ul>
<p>
<a name="EQUALRANGE"></a><a name="l257"></a>
<h3>17.4.10: equal_range()</h3>
    <a name="stl/equalrange"></a>    <a name="an2430"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>pair&lt;ForwardIterator, ForwardIterator&gt;
            equal_range(ForwardIterator </code>
        <code>first, ForwardIterator last, Type const &amp;value);</code>
            <li><code>pair&lt;ForwardIterator, ForwardIterator&gt;
            equal_range(ForwardIterator</code>
        <code>first, ForwardIterator last, Type const &amp;value,
            Compare comp);</code>
        </ul>
        <li> Description (see also identically named member functions of,
e.g., the <code>map</code> (section <a href="cplusplus12.html#MAP">12.3.6</a>) and <code>multimap</code> (section
<a href="cplusplus12.html#MULTIMAP">12.3.7</a>)):
        <ul>
            <li> The first prototype: starting from a sorted sequence (where
the <code>operator&lt;()</code> of the data type to which the iterators point was used to
sort the elements in the provided range), a pair of iterators is returned
representing the return value of, respectively, <code>lower_bound()</code> (returning
the first element that is not smaller than the provided reference value, see
section <a href="cplusplus17.html#LOWERBOUND">17.4.25</a>) and <code>upper_bound()</code>(returning the first element
beyond the provided reference value, see section <a href="cplusplus17.html#UPPERBOUND">17.4.66</a>).
            <li> The second prototype: starting from a sorted sequence (where
the <code>comp</code> function object was used to sort the elements in the provided
range), a pair of iterators is returned representing the return values of,
respectively, the functions <code>lower_bound()</code> (section <a href="cplusplus17.html#LOWERBOUND">17.4.25</a>) and
<code>upper_bound()</code>(section <a href="cplusplus17.html#UPPERBOUND">17.4.66</a>).
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;functional&gt;
    #include &lt;iterator&gt;
    #include &lt;iostream&gt;
    using namespace std;

    int main()
    {
        int                 range[] = {1, 3, 5, 7, 7, 9, 9, 9};
        size_t const      size = sizeof(range) / sizeof(int);

        pair&lt;int *, int *&gt;  pi;

        pi = equal_range(range, range + size, 6);

        cout &lt;&lt; "Lower bound for 6: " &lt;&lt; *pi.first &lt;&lt; endl;
        cout &lt;&lt; "Upper bound for 6: " &lt;&lt; *pi.second &lt;&lt; endl;

        pi = equal_range(range, range + size, 7);

        cout &lt;&lt; "Lower bound for 7: ";
        copy(pi.first, range + size, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        cout &lt;&lt; "Upper bound for 7: ";
        copy(pi.second, range + size, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        sort(range, range + size, greater&lt;int&gt;());

        cout &lt;&lt; "Sorted in descending order\n";

        copy(range, range + size, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        pi = equal_range(range, range + size, 7, greater&lt;int&gt;());

        cout &lt;&lt; "Lower bound for 7: ";
        copy(pi.first, range + size, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        cout &lt;&lt; "Upper bound for 7: ";
        copy(pi.second, range + size, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

                Lower bound for 6: 7
                Upper bound for 6: 7
                Lower bound for 7: 7 7 9 9 9
                Upper bound for 7: 9 9 9
                Sorted in descending order
                9 9 9 7 7 5 3 1
                Lower bound for 7: 7 7 5 3 1
                Upper bound for 7: 5 3 1
    */
</pre>
    </ul>
<p>
<a name="FILL"></a><a name="l258"></a>
<h3>17.4.11: fill()</h3>
    <a name="stl/fill"></a>    <a name="an2431"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>void fill(ForwardIterator first, ForwardIterator last, Type
                const &amp;value);</code>
        </ul>
        <li> Description:
        <ul>
            <li> all the elements implied by the iterator range
<code>[first, last)</code> are initialized to <code>value</code>, overwriting the previous
stored values.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;vector&gt;
    #include &lt;iterator&gt;
    #include &lt;iostream&gt;
    using namespace std;

    int main()
    {
        vector&lt;int&gt;     iv(8);

        fill(iv.begin(), iv.end(), 8);

        copy(iv.begin(), iv.end(), ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        8 8 8 8 8 8 8 8
    */
</pre>
    </ul>
<p>
<a name="FILLN"></a><a name="l259"></a>
<h3>17.4.12: fill_n()</h3>
    <a name="stl/filln"></a>    <a name="an2432"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>void fill_n(ForwardIterator first, Size n, Type
                const &amp;value);</code>
        </ul>
        <li> Description:
        <ul>
            <li> <code>n</code> elements starting at the element pointed to by
<code>first</code> are  initialized to <code>value</code>, overwriting the previous
stored values.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;vector&gt;
    #include &lt;iterator&gt;
    #include &lt;iostream&gt;
    using namespace std;

    int main()
    {
        vector&lt;int&gt;     iv(8);

        fill_n(iv.begin() + 2, 4, 8);

        copy(iv.begin(), iv.end(), ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        0 0 8 8 8 8 0 0
    */
</pre>
    </ul>
<p>
<a name="FIND"></a><a name="l260"></a>
<h3>17.4.13: find()</h3>
    <a name="stl/find"></a>    <a name="an2433"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>InputIterator find(InputIterator first,
    InputIterator last, Type const &amp;value);</code>
        </ul>
        <li> Description:
        <ul>
            <li> Element <code>value</code> is searched for in the range of the elements
implied by the iterator range <code>[first, last)</code>. An iterator pointing to
the first element found is returned. If the element was not found, <code>last</code> is
returned. The <code>operator==()</code> of the underlying data type is used to
compare the elements.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;
    #include &lt;iostream&gt;
    using namespace std;

    int main()
    {
        string sarr[] =
            {
                "alpha", "bravo", "charley", "delta", "echo"
            };
        string  *last = sarr + sizeof(sarr) / sizeof(string);

        copy
        (
            find(sarr, last, "delta"), last, ostream_iterator&lt;string&gt;(cout, " ")
        );
        cout &lt;&lt; endl;

        if (find(sarr, last, "india") == last)
        {
            cout &lt;&lt; "`india' was not found in the range\n";
            copy(sarr, last, ostream_iterator&lt;string&gt;(cout, " "));
            cout &lt;&lt; endl;
        }

        return 0;

    }
    /*
        Generated output:

        delta echo
        `india' was not found in the range
        alpha bravo charley delta echo
    */
</pre>
    </ul>
<p>
<a name="FINDEND"></a><a name="l261"></a>
<h3>17.4.14: find_end()</h3>
    <a name="stl/findend"></a>    <a name="an2434"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>ForwardIterator1 find_end(ForwardIterator1 first1,
    ForwardIterator1 last1,</code>
                <code>ForwardIterator2 first2, ForwardIterator2 last2)</code>
            <li><code>ForwardIterator1 find_end(ForwardIterator1 first1,
    ForwardIterator1 last1,</code>
        <code>ForwardIterator2 first2, ForwardIterator2 last2,
                                            BinaryPredicate pred)</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the sequence of elements implied by
<code>[first1, last1)</code> is searched for the last occurrence of the sequence of
elements implied by <code>[first2, last2)</code>. If the sequence <code>[first2,
last2)</code> is not found, <code>last1</code> is returned, otherwise an iterator pointing to
the first element of the matching sequence is returned. The <code>operator==()</code>
of the underlying data type is used to compare the elements in the two
sequences.
            <li> The second prototype: the sequence of elements implied by
<code>[first1, last1)</code> is searched for the last occurrence of the sequence of
elements implied by <code>[first2, last2)</code>. If the sequence <code>[first2,
last2)</code> is not found, <code>last1</code> is returned, otherwise an iterator pointing to
the first element of the matching sequence is returned. The provided binary
predicate is used to compare the elements in the two sequences.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;
    #include &lt;iostream&gt;

    class Twice
    {
        public:
            bool operator()(size_t first, size_t second) const
            {
                return first == (second &lt;&lt; 1);
            }
    };

    using namespace std;

    int main()
    {
        string sarr[] =
            {
                "alpha", "bravo", "charley", "delta", "echo",
                "foxtrot", "golf", "hotel",
                "foxtrot", "golf", "hotel",
                "india", "juliet", "kilo"
            };
        string search[] =
            {
                "foxtrot",
                "golf",
                "hotel"
            };
        string  *last = sarr + sizeof(sarr) / sizeof(string);

        copy
        (
            find_end(sarr, last, search, search + 3),   // sequence starting
            last, ostream_iterator&lt;string&gt;(cout, " ")   // at 2nd 'foxtrot'
        );
        cout &lt;&lt; endl;

        size_t range[] = {2, 4, 6, 8, 10, 4, 6, 8, 10};
        size_t nrs[]   = {2, 3, 4};

        copy                // sequence of values starting at last sequence
        (                   // of range[] that are twice the values in nrs[]
            find_end(range, range + 9, nrs, nrs + 3, Twice()),
            range + 9, ostream_iterator&lt;size_t&gt;(cout, " ")
        );
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        foxtrot golf hotel india juliet kilo
        4 6 8 10
    */
</pre>
    </ul>
<p>
<a name="FINDFIRST"></a><a name="l262"></a>
<h3>17.4.15: find_first_of()</h3>
    <a name="stl/findfirstof"></a>    <a name="an2435"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>ForwardIterator1 find_first_of(ForwardIterator1 first1,
    ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)</code>
            <li><code>ForwardIterator1 find_first_of(ForwardIterator1 first1,
    ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2,
    BinaryPredicate pred)</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the sequence of elements implied by
<code>[first1, last1)</code> is searched for the first occurrence of an element in
the sequence of elements implied by <code>[first2, last2)</code>. If no element in
the sequence <code>[first2, last2)</code> is found, <code>last1</code> is returned, otherwise
an iterator pointing to the first element in <code>[first1, last1)</code> that is
equal to an element in <code>[first2, last2)</code> is returned. The
<code>operator==()</code> of the underlying data type is used to compare the elements
in the two sequences.
            <li> The second prototype: the sequence of elements implied by
<code>[first1, first1)</code> is searched for the first occurrence of an element in
the sequence of elements implied by <code>[first2, last2)</code>. Each element in
the range <code>[first1, last1)</code> is compared to each element in the range
<code>[first2, last2)</code>, and an iterator to the first element in
<code>[first1, last1)</code> for which the binary predicate <code>pred</code> (receiving an
the element out of the range <code>[first1, last1)</code> and an element from the
range <code>[first2, last2)</code>) returns <code>true</code> is returned. Otherwise,
<code>last1</code> is returned.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;
    #include &lt;iostream&gt;

    class Twice
    {
        public:
            bool operator()(size_t first, size_t second) const
            {
                return first == (second &lt;&lt; 1);
            }
    };

    using namespace std;

    int main()
    {
        string sarr[] =
            {
                "alpha", "bravo", "charley", "delta", "echo",
                "foxtrot", "golf", "hotel",
                "foxtrot", "golf", "hotel",
                "india", "juliet", "kilo"
            };
        string search[] =
            {
                "foxtrot",
                "golf",
                "hotel"
            };
        string  *last = sarr + sizeof(sarr) / sizeof(string);

        copy
        (                                               // sequence starting
            find_first_of(sarr, last, search, search + 3),  // at 1st 'foxtrot'
            last, ostream_iterator&lt;string&gt;(cout, " ")
        );
        cout &lt;&lt; endl;

        size_t range[] = {2, 4, 6, 8, 10, 4, 6, 8, 10};
        size_t nrs[]   = {2, 3, 4};

        copy            // sequence of values starting at first sequence
        (               // of range[] that are twice the values in nrs[]
            find_first_of(range, range + 9, nrs, nrs + 3, Twice()),
            range + 9, ostream_iterator&lt;size_t&gt;(cout, " ")
        );
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        foxtrot golf hotel foxtrot golf hotel india juliet kilo
        4 6 8 10 4 6 8 10
    */
</pre>
    </ul>
<p>
<a name="FINDIF"></a><a name="l263"></a>
<h3>17.4.16: find_if()</h3>
    <a name="stl/findif"></a>    <a name="an2436"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>InputIterator find_if(InputIterator first,
    InputIterator last, Predicate pred);</code>
        </ul>
        <li> Description:
        <ul>
            <li> An iterator pointing to the first element in the range
implied by the iterator range <code>[first, last)</code> for which the (unary)
predicate <code>pred</code> returns <code>true</code> is returned. If the element was not found,
<code>last</code> is returned.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;
    #include &lt;iostream&gt;

    class CaseName
    {
        std::string  d_string;

        public:
            CaseName(char const *str): d_string(str)
            {}
            bool operator()(std::string const &amp;element)
            {
                return !strcasecmp(element.c_str(), d_string.c_str());
            }
    };

    using namespace std;

    int main()
    {
        string sarr[] =
            {
                "Alpha", "Bravo", "Charley", "Delta", "Echo",
            };
        string  *last = sarr + sizeof(sarr) / sizeof(string);

        copy
        (
            find_if(sarr, last, CaseName("charley")),
            last, ostream_iterator&lt;string&gt;(cout, " ")
        );
        cout &lt;&lt; endl;

        if (find_if(sarr, last, CaseName("india")) == last)
        {
            cout &lt;&lt; "`india' was not found in the range\n";
            copy(sarr, last, ostream_iterator&lt;string&gt;(cout, " "));
            cout &lt;&lt; endl;
        }

        return 0;

    }
    /*
        Generated output:

        Charley Delta Echo
        `india' was not found in the range
        Alpha Bravo Charley Delta Echo
    */
</pre>
    </ul>
<p>
<a name="FOREACH"></a><a name="l264"></a>
<h3>17.4.17: for_each()</h3>
    <a name="stl/foreach"></a>    <a name="an2437"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>Function for_each(ForwardIterator first,
    ForwardIterator last, Function func);</code>
        </ul>
        <li> Description:
        <ul>
            <li> Each of the elements implied by the iterator range
<code>[first, last)</code> is passed in turn as a reference to the function (or
function object) <code>func</code>. The function may modify the elements it receives
(as the used iterator is a forward iterator). Alternatively, if the elements
should be transformed, <code>transform()</code> (see section <a href="cplusplus17.html#TRANSFORM">17.4.63</a>) can be
used. The function itself or a copy of the provided function object is
returned: see the example below, in which an extra argument list is added to
the <code>for_each()</code> call, which argument is eventually also passed to the
function given to <code>for_each()</code>. Within <code>for_each()</code> the return value of
the function that is passed to it is ignored.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;string&gt;
    #include &lt;iostream&gt;
    #include &lt;cctype&gt;

    void lowerCase(char &amp;c)                     // `c' *is* modified
    {
        c = static_cast&lt;char&gt;(tolower(c));
    }
                                                // `str' is *not* modified
    void capitalizedOutput(std::string const &amp;str)
    {
        char    *tmp = strcpy(new char[str.size() + 1], str.c_str());

        std::for_each(tmp + 1, tmp + str.size(), lowerCase);

        tmp[0] = toupper(*tmp);
        std::cout &lt;&lt; tmp &lt;&lt; " ";
        delete tmp;
    };

    using namespace std;

    int main()
    {
        string sarr[] =
            {
                "alpha", "BRAVO", "charley", "DELTA",  "echo",
                "FOXTROT", "golf", "HOTEL",
            };
        string *last = sarr + sizeof(sarr) / sizeof(string);

        for_each(sarr, last, capitalizedOutput)("that's all, folks");
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        Alpha Bravo Charley Delta Echo Foxtrot Golf Hotel That's all, folks
    */
</pre>
        <li> Here is another example, using a function object:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;string&gt;
    #include &lt;iostream&gt;
    #include &lt;cctype&gt;

    void lowerCase(char &amp;c)
    {
        c = tolower(c);
    }

    class Show
    {
        int d_count;

        public:
            Show()
            :
                d_count(0)
            {}

            void operator()(std::string &amp;str)
            {
                std::for_each(str.begin(), str.end(), lowerCase);
                str[0] = toupper(str[0]);   // here assuming str.length()
                std::cout &lt;&lt; ++d_count &lt;&lt; " " &lt;&lt; str &lt;&lt; "; ";
            }

            int count() const
            {
                return d_count;
            }
    };

    using namespace std;

    int main()
    {
        string sarr[] =
            {
                "alpha", "BRAVO", "charley", "DELTA", "echo",
                "FOXTROT", "golf", "HOTEL",
            };
        string *last = sarr + sizeof(sarr) / sizeof(string);

        cout &lt;&lt; for_each(sarr, last, Show()).count() &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output (all on a single line):

        1 Alpha; 2 Bravo; 3 Charley; 4 Delta; 5 Echo; 6 Foxtrot;
                                                      7 Golf; 8 Hotel; 8
    */
</pre>
    </ul>
    The example also shows that the <code>for_each</code> algorithm may be used with
functions defining <code>const</code> and non-<code>const</code> parameters. Also, see section
<a href="cplusplus17.html#TRANSFORM">17.4.63</a> for differences between the <code>for_each()</code> and <code>transform()</code>
generic algorithms.
<p>
The <code>for_each()</code> algorithm cannot directly be used (i.e., by passing
<code>*this</code> as the function object argument) inside a member function to modify
its own object as the <code>for_each()</code> algorithm first creates its own copy of
the passed function object. A <a name="an2438"></a>
<em>wrapper class</em> whose constructor accepts a
pointer or reference to the current object and possibly to one of its member
functions solves this problem. In section <a href="cplusplus20.html#STLWRAPPERS">20.7</a> the construction
of such wrapper classes is described.
<p>
<a name="GEN"></a><a name="l265"></a>
<h3>17.4.18: generate()</h3>
    <a name="stl/generate"></a>    <a name="an2439"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>void generate(ForwardIterator first,
                ForwardIterator last,</code>
                <code>Generator generator);</code>
        </ul>
        <li> Description:
        <ul>
            <li> All elements implied by the iterator range <code>[first,
last)</code> are initialized by the return value of <code>generator</code>, which can be a
function or function object. <code>Generator::operator()()</code> does not receive
any arguments. The example uses a well-known fact from algebra: in order to
obtain the square of <code>n + 1</code>, add <code>1 + 2 * n</code> to <code>n * n</code>.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;vector&gt;
    #include &lt;iterator&gt;
    #include &lt;iostream&gt;

    class NaturalSquares
    {
        size_t d_newsqr;
        size_t d_last;

        public:
            NaturalSquares(): d_newsqr(0), d_last(0)
            {}
            size_t operator()()
            {                   // using: (a + 1)^2 == a^2 + 2*a + 1
                return d_newsqr += (d_last++ &lt;&lt; 1) + 1;
            }
    };

    using namespace std;

    int main()
    {
        vector&lt;size_t&gt;    uv(10);

        generate(uv.begin(), uv.end(), NaturalSquares());

        copy(uv.begin(), uv.end(), ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        1 4 9 16 25 36 49 64 81 100
    */
</pre>
    </ul>
<p>
<a name="GENN"></a><a name="l266"></a>
<h3>17.4.19: generate_n()</h3>
    <a name="stl/generaten"></a>    <a name="an2440"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>void generate_n(ForwardIterator first, Size n,
                Generator generator);</code>
        </ul>
        <li> Description:
        <ul>
            <li> <code>n</code> elements starting at the element pointed to by
iterator <code>first</code> are initialized by the return value of <code>generator</code>,
which can be a function or function object.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;vector&gt;
    #include &lt;iterator&gt;
    #include &lt;iostream&gt;

    class NaturalSquares
    {
        size_t d_newsqr;
        size_t d_last;

        public:
            NaturalSquares(): d_newsqr(0), d_last(0)
            {}
            size_t operator()()
            {                           // using: (a + 1)^2 == a^2 + 2*a + 1
                return d_newsqr += (d_last++ &lt;&lt; 1) + 1;
            }
    };

    using namespace std;

    int main()
    {
        vector&lt;size_t&gt;    uv(10);

        generate_n(uv.begin(), 5, NaturalSquares());

        copy(uv.begin(), uv.end(), ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        1 4 9 16 25 0 0 0 0 0
    */
</pre>
    </ul>
<p>
<a name="INCLUDES"></a><a name="l267"></a>
<h3>17.4.20: includes()</h3>
    <a name="stl/includes"></a>    <a name="an2441"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);</code>
            <li><code>bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: both sequences of elements implied by
the ranges <code>[first1, last1)</code> and <code>[first2, last2)</code> should be sorted,
using the <code>operator&lt;()</code> of the data type to which the iterators point. The
function returns <code>true</code> if every element in the second sequence
<code>[first2, second2)</code> is contained in the first sequence <code>[first1,
second1)</code> (the second range is a subset of the first range).
            <li> The second prototype: both sequences of elements implied by
the ranges <code>[first1, last1)</code> and <code>[first2, last2)</code> should be sorted,
using the <code>comp</code> function object. The function returns <code>true</code> if every
element in the second sequence <code>[first2, second2)</code> is contained in the
first seqence <code>[first1, second1)</code> (the second range is a subset of the
first range).
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;string&gt;
    #include &lt;iostream&gt;

    class CaseString
    {
        public:
            bool operator()(std::string const &amp;first,
                            std::string const &amp;second) const
            {
                return !strcasecmp(first.c_str(), second.c_str());
            }
    };

    using namespace std;

    int main()
    {
        string first1[] =
            {
                "alpha", "bravo", "charley", "delta",  "echo",
                "foxtrot", "golf", "hotel"
            };
        string first2[] =
            {
                "Alpha", "bravo", "Charley", "delta",  "Echo",
                "foxtrot", "Golf", "hotel"
            };
        string second[] =
            {
                "charley", "foxtrot", "hotel"
            };
        size_t n = sizeof(first1) / sizeof(string);

        cout &lt;&lt; "The elements of `second' are " &lt;&lt;
            (includes(first1, first1 + n, second, second + 3) ? "" : "not")
            &lt;&lt; " contained in the first sequence:\n"
               "second is a subset of first1\n";

        cout &lt;&lt; "The elements of `first1' are " &lt;&lt;
            (includes(second, second + 3, first1, first1 + n) ? "" : "not")
            &lt;&lt; " contained in the second sequence\n";

        cout &lt;&lt; "The elements of `second' are " &lt;&lt;
            (includes(first2, first2 + n, second, second + 3) ? "" : "not")
            &lt;&lt; " contained in the first2 sequence\n";

        cout &lt;&lt; "Using case-insensitive comparison,\n"
            "the elements of `second' are "
            &lt;&lt;
            (includes(first2, first2 + n, second, second + 3, CaseString()) ?
                "" : "not")
            &lt;&lt; " contained in the first2 sequence\n";

        return 0;
    }
    /*
        Generated output:

        The elements of `second' are  contained in the first sequence:
        second is a subset of first1
        The elements of `first1' are not contained in the second sequence
        The elements of `second' are not contained in the first2 sequence
        Using case-insensitive comparison,
        the elements of `second' are  contained in the first2 sequence
    */
</pre>
    </ul>
<p>
<a name="INNERPROD"></a><a name="l268"></a>
<h3>17.4.21: inner_product()</h3>
    <a name="stl/innerproduct"></a>    <a name="an2442"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;numeric&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>Type inner_product(InputIterator1 first1,
                InputIterator1 last1,</code>
                <code>InputIterator2 first2, Type init);</code>
            <li><code>Type inner_product(InputIterator1 first1,
                InputIterator1 last1,</code>
                <code>InputIterator2 first2, Type init, BinaryOperator1 op1,
                    BinaryOperator2 op2);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the sum of all pairwise products of the
elements implied by the range <code>[first1, last1)</code> and the same number of
elements starting at the element pointed to by <code>first2</code>
are added to <code>init</code>, and this sum is returned. The function uses the
<code>operator+()</code> and <code>operator*()</code> of the data type to which the iterators
point.
            <li> The second prototype: binary operator <code>op1</code> instead of the
default addition operator, and binary operator <code>op2</code> instead of the default
multiplication operator are applied to all pairwise elements implied by the
range <code>[first1, last1)</code> and the same number of elements starting at the
element pointed to by <code>first2</code>. The final result is returned.
        </ul>
        <li> Example:
        <pre>
    #include &lt;numeric&gt;
    #include &lt;algorithm&gt;
    #include &lt;iterator&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;

    class Cat
    {
        std::string  d_sep;
        public:
            Cat(std::string const &amp;sep)
            :
                d_sep(sep)
            {}
            std::string operator()
                (std::string const &amp;s1, std::string const &amp;s2) const
            {
                return s1 + d_sep + s2;
            }
    };

    using namespace std;

    int main()
    {
        size_t ia1[] = {1, 2, 3, 4, 5, 6, 7};
        size_t ia2[] = {7, 6, 5, 4, 3, 2, 1};
        size_t init = 0;

        cout &lt;&lt; "The sum of all squares in ";
        copy(ia1, ia1 + 7, ostream_iterator&lt;size_t&gt;(cout, " "));
        cout &lt;&lt; "is " &lt;&lt;
            inner_product(ia1, ia1 + 7, ia1, init) &lt;&lt; endl;

        cout &lt;&lt; "The sum of all cross-products in ";
        copy(ia1, ia1 + 7, ostream_iterator&lt;size_t&gt;(cout, " "));
        cout &lt;&lt; " and ";
        copy(ia2, ia2 + 7, ostream_iterator&lt;size_t&gt;(cout, " "));
        cout &lt;&lt; "is " &lt;&lt;
            inner_product(ia1, ia1 + 7, ia2, init) &lt;&lt; endl;

        string names1[] = {"Frank", "Karel", "Piet"};
        string names2[] = {"Brokken", "Kubat", "Plomp"};

        cout &lt;&lt; "A list of all combined names in ";
        copy(names1, names1 + 3, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; "and\n";
        copy(names2, names2 + 3, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; "is:" &lt;&lt;
            inner_product(names1, names1 + 3, names2, string("\t"),
                Cat("\n\t"), Cat(" ")) &lt;&lt;
            endl;

        return 0;
    }
    /*
        Generated output:

        The sum of all squares in 1 2 3 4 5 6 7 is 140
        The sum of all cross-products in 1 2 3 4 5 6 7  and 7 6 5 4 3 2 1 is 84
        A list of all combined names in Frank Karel Piet and
        Brokken Kubat Plomp is:
                Frank Brokken
                Karel Kubat
                Piet Plomp
    */
</pre>
    </ul>
<p>
<a name="INMERGE"></a><a name="l269"></a>
<h3>17.4.22: inplace_merge()</h3>
    <a name="stl/inplacemerge"></a>    <a name="an2443"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>void inplace_merge(BidirectionalIterator first,
BidirectionalIterator</code>
                <code>middle, BidirectionalIterator last);</code>
            <li><code>void inplace_merge(BidirectionalIterator first,
BidirectionalIterator </code>
            <code>middle, BidirectionalIterator last, Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the two (sorted) ranges <code>[first,
middle)</code> and <code>[middle, last)</code> are merged, keeping a sorted list (using the
<code>operator&lt;()</code> of the data type to which the iterators point). The final
series is stored in the range <code>[first, last)</code>.
            <li> The second prototype: the two (sorted) ranges <code>[first,
middle)</code> and <code>[middle, last)</code> are merged, keeping a sorted list (using the
boolean result of the binary comparison operator <code>comp</code>). The final series
is stored in the range <code>[first, last)</code>.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;
    #include &lt;iostream&gt;

    class CaseString
    {
        public:
            bool operator()(std::string const &amp;first,
                            std::string const &amp;second) const
            {
                return strcasecmp(first.c_str(), second.c_str()) &lt; 0;
            }
    };

    using namespace std;

    int main()
    {
        string range[] =
            {
                "alpha", "charley", "echo", "golf",
                "bravo", "delta", "foxtrot",
            };

        inplace_merge(range, range + 4, range + 7);
        copy(range, range + 7, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        string range2[] =
            {
                "ALFA", "CHARLEY", "DELTA", "foxtrot", "hotel",
                "bravo", "ECHO", "GOLF"
            };

        inplace_merge(range2, range2 + 5, range2 + 8, CaseString());
        copy(range2, range2 + 8, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        alpha bravo charley delta echo foxtrot golf
        ALFA bravo CHARLEY DELTA ECHO foxtrot GOLF hotel
    */
</pre>
    </ul>
<p>
<a name="ITERSWAP"></a><a name="l270"></a>
<h3>17.4.23: iter_swap()</h3>
    <a name="stl/iterswap"></a>    <a name="an2444"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>void iter_swap(ForwardIterator1 iter1,
ForwardIterator2 iter2);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The elements pointed to by <code>iter1</code> and <code>iter2</code> are
swapped.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iterator&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    using namespace std;

    int main()
    {
        string first[] = {"alpha", "bravo", "charley"};
        string second[] = {"echo", "foxtrot", "golf"};
        size_t const n = sizeof(first) / sizeof(string);

        cout &lt;&lt; "Before:\n";
        copy(first, first + n, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;
        copy(second, second + n, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        for (size_t idx = 0; idx &lt; n; ++idx)
            iter_swap(first + idx, second + idx);

        cout &lt;&lt; "After:\n";
        copy(first, first + n, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;
        copy(second, second + n, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        Before:
        alpha bravo charley
        echo foxtrot golf
        After:
        echo foxtrot golf
        alpha bravo charley
    */
</pre>
    </ul>
<p>
<a name="LEXCOMP"></a><a name="l271"></a>
<h3>17.4.24: lexicographical_compare()</h3>
    <a name="stl/lexicographicalcompare"></a>    <a name="an2445"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>bool lexicographical_compare(InputIterator1 first1,
InputIterator1 last1,</code>
                <code>InputIterator2 first2, InputIterator2 last2);</code>
            <li><code>bool lexicographical_compare(InputIterator1 first1,
InputIterator1 last1,</code>
        <code>InputIterator2 first2, InputIterator2 last2,
            Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the corresponding pairs of elements in
the ranges pointed to by <code>[first1, last1)</code> and <code>[first2, last2)</code> are
compared. The function returns <a name="an2446"></a>
<code>true</code>
            <ul>
                <li> at the first element in the first range which is less
than the corresponding element in the second range (using <code>operator&lt;()</code>
of the underlying data type),
                <li> if <code>last1</code> is reached, but <code>last2</code> isn't reached yet.
            </ul>
False is returned in the other cases, which indicates that the first sequence
is not lexicographical less than the second sequence. So, <a name="an2447"></a>
<code>false</code> is
returned:
            <ul>
                <li> at the first element in the first range which is greater
than the corresponding element in the second range (using <code>operator&lt;()</code>
of the data type to which the iterators point, reversing the  operands),
                <li> if <code>last2</code> is reached, but <code>last1</code> isn't reached yet,
                <li> if <code>last1</code> and <code>last2</code> are reached.
            </ul>
            <li> The second prototype: with this function the binary
comparison operation as defined by <code>comp</code> is used instead of
<code>operator&lt;()</code> of the data type to which the iterators point.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iterator&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;

    class CaseString
    {
        public:
            bool operator()(std::string const &amp;first,
                            std::string const &amp;second) const
            {
                return strcasecmp(first.c_str(), second.c_str()) &lt; 0;
            }
    };

    using namespace std;

    int main()
    {
        string word1 = "hello";
        string word2 = "help";

        cout &lt;&lt; word1 &lt;&lt; " is " &lt;&lt;
            (
                lexicographical_compare(word1.begin(), word1.end(),
                                        word2.begin(), word2.end()) ?
                    "before "
                :
                    "beyond or at "
            ) &lt;&lt;
            word2 &lt;&lt; " in the alphabet\n";

        cout &lt;&lt; word1 &lt;&lt; " is " &lt;&lt;
            (
                lexicographical_compare(word1.begin(), word1.end(),
                                        word1.begin(), word1.end()) ?
                    "before "
                :
                    "beyond or at "
            ) &lt;&lt;
            word1 &lt;&lt; " in the alphabet\n";

        cout &lt;&lt; word2 &lt;&lt; " is " &lt;&lt;
            (
                lexicographical_compare(word2.begin(), word2.end(),
                                        word1.begin(), word1.end()) ?
                    "before "
                :
                    "beyond or at "
            ) &lt;&lt;
            word1 &lt;&lt; " in the alphabet\n";

        string one[] = {"alpha", "bravo", "charley"};
        string two[] = {"ALPHA", "BRAVO", "DELTA"};

        copy(one, one + 3, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; " is ordered " &lt;&lt;
            (
                lexicographical_compare(one, one + 3,
                                        two, two + 3, CaseString()) ?
                    "before "
                :
                    "beyond or at "
            );
        copy(two, two + 3, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl &lt;&lt;
            "using case-insensitive comparisons.\n";

        return 0;
    }
    /*
        Generated output:

        hello is before help in the alphabet
        hello is beyond or at hello in the alphabet
        help is beyond or at hello in the alphabet
        alpha bravo charley  is ordered before ALPHA BRAVO DELTA
        using case-insensitive comparisons.
    */
</pre>
    </ul>
<p>
<a name="LOWERBOUND"></a><a name="l272"></a>
<h3>17.4.25: lower_bound()</h3>
    <a name="stl/lowerbound"></a>    <a name="an2448"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>ForwardIterator lower_bound(ForwardIterator first,
ForwardIterator last,</code><code>const Type &amp;value);</code>
            <li><code>ForwardIterator lower_bound(ForwardIterator first,
ForwardIterator last,</code><code>const Type &amp;value, Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the sorted elements indicated by the
iterator range <code>[first, last)</code> are searched for the first element that is
not less than (i.e., greater than or equal to) <code>value</code>. The returned
iterator marks the location in the sequence where <code>value</code> can be inserted
without breaking the sorted order of the elements. The <code>operator&lt;()</code> of the
data type to which the iterators point is used. If no such element is found,
<code>last</code> is returned.
            <li> The second prototype: the elements indicated by the iterator
range <code>[first, last)</code> must have been sorted using the <code>comp</code> function
(-object). Each element in the range is compared to <code>value</code> using the
<code>comp</code> function. An iterator to the first element for which the binary
predicate <code>comp</code>, applied to the elements of the range and <code>value</code>,
returns <code>false</code> is returned.  If no such element is found, <code>last</code> is
returned.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;iterator&gt;
    #include &lt;functional&gt;
    using namespace std;

    int main()
    {
        int     ia[] = {10, 20, 30};

        cout &lt;&lt; "Sequence: ";
        copy(ia, ia + 3, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        cout &lt;&lt; "15 can be inserted before " &lt;&lt;
                *lower_bound(ia, ia + 3, 15) &lt;&lt; endl;
        cout &lt;&lt; "35 can be inserted after " &lt;&lt;
                (lower_bound(ia, ia + 3, 35) == ia + 3 ?
                                    "the last element" : "???") &lt;&lt; endl;

        iter_swap(ia, ia + 2);

        cout &lt;&lt; "Sequence: ";
        copy(ia, ia + 3, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        cout &lt;&lt; "15 can be inserted before " &lt;&lt;
                *lower_bound(ia, ia + 3, 15, greater&lt;int&gt;()) &lt;&lt; endl;
        cout &lt;&lt; "35 can be inserted before " &lt;&lt;
                (lower_bound(ia, ia + 3, 35, greater&lt;int&gt;()) == ia ?
                                    "the first element " : "???") &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        Sequence: 10 20 30
        15 can be inserted before 20
        35 can be inserted after the last element
        Sequence: 30 20 10
        15 can be inserted before 10
        35 can be inserted before the first element
    */
</pre>
    </ul>
<p>
<a name="MAX"></a><a name="l273"></a>
<h3>17.4.26: max()</h3>
    <a name="stl/max"></a>    <a name="an2449"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>Type const &amp;max(Type const &amp;one, Type const &amp;two);</code>
            <li><code>Type const &amp;max(Type const &amp;one, Type const &amp;two, Comparator
                comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the larger of the two elements <code>one</code>
and <code>two</code> is returned, using the <code>operator&gt;()</code> of the data type to which
the iterators point.
            <li> The second prototype: <code>one</code> is returned if the binary
predicate <code>comp(one, two)</code> returns <code>true</code>, otherwise <code>two</code> is returned.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;

    class CaseString
    {
        public:
            bool operator()(std::string const &amp;first,
                            std::string const &amp;second) const
            {
                return strcasecmp(second.c_str(), first.c_str()) &gt; 0;
            }
    };

    using namespace std;

    int main()
    {
        cout &lt;&lt; "Word '" &lt;&lt; max(string("first"), string("second")) &lt;&lt;
                                    "' is lexicographically last\n";

        cout &lt;&lt; "Word '" &lt;&lt; max(string("first"), string("SECOND")) &lt;&lt;
                                    "' is lexicographically last\n";

        cout &lt;&lt; "Word '" &lt;&lt; max(string("first"), string("SECOND"),
                            CaseString()) &lt;&lt; "' is lexicographically last\n";

        return 0;
    }
    /*
        Generated output:

        Word 'second' is lexicographically last
        Word 'first' is lexicographically last
        Word 'SECOND' is lexicographically last
    */
</pre>
    </ul>
<p>
<a name="MAXEL"></a><a name="l274"></a>
<h3>17.4.27: max_element()</h3>
    <a name="stl/maxelement"></a>    <a name="an2450"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>ForwardIterator max_element(ForwardIterator first,
ForwardIterator last);</code>
            <li><code>ForwardIterator max_element(ForwardIterator first,
ForwardIterator last,</code><code>Comparator comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: an iterator pointing to the largest
element in the range implied by <code>[first, last)</code> is returned. The
<a name="an2451"></a>
<code>operator&lt;()</code> of the data type to which the iterators point is used.
            <li> The second prototype: rather than using <code>operator&lt;()</code>, the
binary predicate <code>comp</code> is used to make the comparisons between the elements
implied by the iterator range <code>[first, last)</code>. The element for which
<code>comp</code> returns most often <code>true</code>, compared with other elements, is
returned.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;

    class AbsValue
    {
        public:
            bool operator()(int first, int second) const
            {
                return abs(first) &lt; abs(second);
            }
    };

    using namespace std;

    int main()
    {
        int     ia[] = {-4, 7, -2, 10, -12};

        cout &lt;&lt; "The max. int value is " &lt;&lt; *max_element(ia, ia + 5) &lt;&lt; endl;
        cout &lt;&lt; "The max. absolute int value is " &lt;&lt;
                *max_element(ia, ia + 5, AbsValue()) &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        The max. int value is 10
        The max. absolute int value is -12
    */
</pre>
    </ul>
<p>
<a name="MERGE"></a><a name="l275"></a>
<h3>17.4.28: merge()</h3>
    <a name="stl/merge"></a>    <a name="an2452"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>OutputIterator merge(InputIterator1 first1,
InputIterator1 last1,</code>
            <code>InputIterator2 first2, InputIterator2 last2,
                    OutputIterator result);</code>
            <li><code>OutputIterator merge(InputIterator1 first1,
InputIterator1 last1,</code><code>InputIterator2 first2, InputIterator2
last2, OutputIterator result,</code> <code>Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the two (sorted) ranges <code>[first1,
last1)</code> and <code>[first2, last2)</code> are merged, keeping a sorted list (using the
<a name="an2453"></a>
<code>operator&lt;()</code> of the data type to which the iterators point). The final
series is stored in the range starting at <code>result</code> and ending just before
the <code>OutputIterator</code> returned by the function.
            <li> The first prototype: the two (sorted) ranges <code>[first1,
last1)</code> and <code>[first2, last2)</code> are merged, keeping a sorted list (using the
boolean result of the binary comparison operator <code>comp</code>). The final series
is stored in the range starting at <code>result</code> and ending just before the
<code>OutputIterator</code> returned by the function.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;
    #include &lt;iostream&gt;

    class CaseString
    {
        public:
            bool operator()(std::string const &amp;first,
                            std::string const &amp;second) const
            {
                return strcasecmp(first.c_str(), second.c_str()) &lt; 0;
            }
    };

    using namespace std;

    int main()
    {
        string range1[] =
            {                                       // 5 elements
                "alpha", "bravo", "foxtrot", "hotel", "zulu"
            };
        string range2[] =
            {                                       // 4 elements
                "echo", "delta", "golf", "romeo"
            };
        string result[5 + 4];


        copy(result,
            merge(range1, range1 + 5, range2, range2 + 4, result),
            ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        string range3[] =
            {
                "ALPHA", "bravo", "foxtrot", "HOTEL", "ZULU"
            };
        string range4[] =
            {
                "delta", "ECHO", "GOLF", "romeo"
            };

        copy(result,
            merge(range3, range3 + 5, range4, range4 + 4, result,
                                                            CaseString()),
            ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        alpha bravo echo delta foxtrot golf hotel romeo zulu
        ALPHA bravo delta ECHO foxtrot GOLF HOTEL romeo ZULU
    */
</pre>
    </ul>
<p>
<a name="MIN"></a><a name="l276"></a>
<h3>17.4.29: min()</h3>
    <a name="stl/min"></a>    <a name="an2454"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>Type const &amp;min(Type const &amp;one, Type const &amp;two);</code>
            <li><code>Type const &amp;min(Type const &amp;one, Type const &amp;two, Comparator
                comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the smaller of the two elements <code>one</code>
and <code>two</code> is returned, using the <code>operator&lt;()</code> of the data type to which
the iterators point.
            <li> The second prototype: <code>one</code> is returned if the binary
predicate <code>comp(one, two)</code> returns <code>false</code>, otherwise <code>two</code> is returned.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;

    class CaseString
    {
        public:
            bool operator()(std::string const &amp;first,
                            std::string const &amp;second) const
            {
                return strcasecmp(second.c_str(), first.c_str()) &gt; 0;
            }
    };

    using namespace std;

    int main()
    {
        cout &lt;&lt; "Word '" &lt;&lt; min(string("first"), string("second")) &lt;&lt;
                                    "' is lexicographically first\n";

        cout &lt;&lt; "Word '" &lt;&lt; min(string("first"), string("SECOND")) &lt;&lt;
                                    "' is lexicographically first\n";

        cout &lt;&lt; "Word '" &lt;&lt; min(string("first"), string("SECOND"),
                            CaseString()) &lt;&lt; "' is lexicographically first\n";

        return 0;
    }
    /*
        Generated output:

        Word 'first' is lexicographically first
        Word 'SECOND' is lexicographically first
        Word 'first' is lexicographically first
    */
</pre>
    </ul>
<p>
<a name="MINEL"></a><a name="l277"></a>
<h3>17.4.30: min_element()</h3>
    <a name="stl/minelement"></a>    <a name="an2455"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>ForwardIterator min_element(ForwardIterator first,
ForwardIterator last);</code>
            <li><code>ForwardIterator min_element(ForwardIterator first,
ForwardIterator last,</code><code>Comparator comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: an iterator pointing to the smallest
element in the range implied by <code>[first, last)</code> is returned, using
<code>operator&lt;()</code> of the data type to which the iterators point.
            <li> The second prototype: rather than using <code>operator&lt;()</code>, the
binary predicate <code>comp</code> is used to make the comparisons between the elements
implied by the iterator range <code>[first, last)</code>. The element for which
<code>comp</code> returns <code>false</code> most often is returned.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;

    class AbsValue
    {
        public:
            bool operator()(int first, int second) const
            {
                return abs(first) &lt; abs(second);
            }
    };

    using namespace std;

    int main()
    {
        int     ia[] = {-4, 7, -2, 10, -12};

        cout &lt;&lt; "The minimum int value is " &lt;&lt; *min_element(ia, ia + 5) &lt;&lt;
                endl;
        cout &lt;&lt; "The minimum absolute int value is " &lt;&lt;
                *min_element(ia, ia + 5, AbsValue()) &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        The minimum int value is -12
        The minimum absolute int value is -2
    */
</pre>
    </ul>
<p>
<a name="MISMATCH"></a><a name="l278"></a>
<h3>17.4.31: mismatch()</h3>
    <a name="stl/mismatch"></a>    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>pair&lt;InputIterator1, InputIterator2&gt;
                mismatch(InputIterator1 first1,</code>
                <code>InputIterator1 last1, InputIterator2 first2);</code>
            <li><code>pair&lt;InputIterator1, InputIterator2&gt;
                mismatch(InputIterator1 first1,</code>
                <code>InputIterator1 last1, InputIterator2 first2,
                Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the two sequences of elements starting
at <code>first1</code> and <code>first2</code> are compared using the equality operator of the
data type to which the iterators point. Comparison stops if the compared
elements differ (i.e., <code>operator==()</code> returns false) or <code>last1</code> is
reached. A <code>pair</code> containing iterators pointing to the final positions is
returned. The second sequence may contain more elements than the first
sequence. The behavior of the algorithm is undefined if the second sequence
contains fewer elements than the first sequence.
            <li> The second prototype: the two sequences of elements starting
at <code>first1</code> and <code>first2</code> are compared using the binary comparison
operation as defined by <code>comp</code>, instead of
<code>operator==()</code>. Comparison stops if the <code>comp</code> function returns <code>false</code>
or <code>last1</code> is reached. A <code>pair</code> containing iterators pointing to the final
positions is returned. The second sequence may contain more elements than the
first sequence. The behavior of the algorithm is undefined if the second
sequence contains fewer elements than the first sequence.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;string&gt;
    #include &lt;iostream&gt;
    #include &lt;utility&gt;

    class CaseString
    {
        public:
            bool operator()(std::string const &amp;first,
                            std::string const &amp;second) const
            {
                return strcasecmp(first.c_str(), second.c_str()) == 0;
            }
    };

    using namespace std;

    int main()
    {
        string range1[] =
            {
                "alpha", "bravo", "foxtrot", "hotel", "zulu"
            };
        string range2[] =
            {
                "alpha", "bravo", "foxtrot", "Hotel", "zulu"
            };
        pair&lt;string *, string *&gt; pss = mismatch(range1, range1 + 5, range2);

        cout &lt;&lt; "The elements " &lt;&lt; *pss.first &lt;&lt; " and " &lt;&lt; *pss.second &lt;&lt;
                " at offset " &lt;&lt; (pss.first - range1) &lt;&lt; " differ\n";
        if
        (
            mismatch(range1, range1 + 5, range2, CaseString()).first
            ==
            range1 + 5
        )
            cout &lt;&lt; "When compared case-insensitively they match\n";

        return 0;
    }
    /*
        Generated output:

        The elements hotel and Hotel at offset 3 differ
        When compared case-insensitively they match
    */
</pre>
    </ul>
<p>
<a name="NEXTPERM"></a><a name="l279"></a>
<h3>17.4.32: next_permutation()</h3>
    <a name="stl/nextpermutation"></a>    <a name="an2456"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>bool next_permutation(BidirectionalIterator first,
                BidirectionalIterator last);</code>
            <li><code>bool next_permutation(BidirectionalIterator first,
                BidirectionalIterator</code><code>last, Comp comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the next permutation, given the sequence
of elements in the range <code>[first, last)</code>, is determined. For example, if
the elements <code>1, 2</code> and <code>3</code> are the range for which <code>next_permutation()</code>
is called, then subsequent calls of <code>next_permutation()</code> reorders the
following series:
    <pre>
        1 2 3
        1 3 2
        2 1 3
        2 3 1
        3 1 2
        3 2 1
</pre>
    This example shows that the elements are reordered such that each new
permutation represents the next bigger value (132 is bigger than 123, 213 is
bigger than 132, etc.), using <a name="an2457"></a>
<code>operator&lt;()</code> of the data type to which the
iterators point.  The value <a name="an2458"></a>
<code>true</code> is returned if a reordering took place,
the value <a name="an2459"></a>
<code>false</code> is returned if no reordering took place, which is the case
if the sequence represents the last (biggest) value. In that case, the
sequence is also sorted using <code>operator&lt;()</code>.
        <li> The second prototype: the next permutation given the sequence
of elements in the range <code>[first, last)</code> is determined. The elements in
the range are reordered. The value <code>true</code> is returned if a reordering took
place, the value <code>false</code> is returned if no reordering took place, which is
the case if the resulting sequence would haven been ordered, using the
binary predicate <code>comp</code> to compare elements.
        <li> Example:
            <pre>
    #include &lt;algorithm&gt;
    #include &lt;iterator&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;

    class CaseString
    {
        public:
            bool operator()(std::string const &amp;first,
                            std::string const &amp;second) const
            {
                return strcasecmp(first.c_str(), second.c_str()) &lt; 0;
            }
    };

    using namespace std;

    int main()
    {
        string saints[] = {"Oh", "when", "the", "saints"};

        cout &lt;&lt; "All permutations of 'Oh when the saints':\n";

        cout &lt;&lt; "Sequences:\n";
        do
        {
            copy(saints, saints + 4, ostream_iterator&lt;string&gt;(cout, " "));
            cout &lt;&lt; endl;
        }
        while (next_permutation(saints, saints + 4, CaseString()));


        cout &lt;&lt; "After first sorting the sequence:\n";

        sort(saints, saints + 4, CaseString());

        cout &lt;&lt; "Sequences:\n";
        do
        {
            copy(saints, saints + 4, ostream_iterator&lt;string&gt;(cout, " "));
            cout &lt;&lt; endl;
        }
        while (next_permutation(saints, saints + 4, CaseString()));

        return 0;
    }
    /*
        Generated output (only partially given):

        All permutations of 'Oh when the saints':
        Sequences:
        Oh when the saints
        saints Oh the when
        saints Oh when the
        saints the Oh when
        ...
        After first sorting the sequence:
        Sequences:
        Oh saints the when
        Oh saints when the
        Oh the saints when
        Oh the when saints
        ...
    */
</pre>
        </ul>
    </ul>
<p>
<a name="NTHEL"></a><a name="l280"></a>
<h3>17.4.33: nth_element()</h3>
    <a name="stl/nthelement"></a>    <a name="an2460"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>void nth_element(RandomAccessIterator first,
RandomAccessIterator nth,</code>
        <code>RandomAccessIterator</code> <code>last);</code>
            <li><code>void nth_element(RandomAccessIterator first,
RandomAccessIterator nth,</code>
                <code>RandomAccessIterator last, Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: all elements in the range <code>[first,
last)</code> are sorted relative to the element pointed to by <code>nth</code>: all elements
in the range <code>[left, nth)</code> are smaller than the element pointed to by
<code>nth</code>, and alle elements in the range <code>[nth + 1, last)</code> are greater
than the element pointed to by <code>nth</code>. The two subsets themselves are not
sorted. The <code>operator&lt;()</code> of the data type to which the iterators point is
used to compare the elements.
            <li> The second prototype: all elements in the range <code>[first,
last)</code> are sorted relative to the element pointed to by <code>nth</code>: all elements
in the range <code>[left, nth)</code> are smaller than the element pointed to by
<code>nth</code>, and alle elements in the range <code>[nth + 1, last)</code> are greater
than the element pointed to by <code>nth</code>. The two subsets themselves are not
sorted. The <code>comp</code> function object is used to compare the elements.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;iterator&gt;
    #include &lt;functional&gt;
    using namespace std;

    int main()
    {
        int ia[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};

        nth_element(ia, ia + 3, ia + 10);

        cout &lt;&lt; "sorting with respect to " &lt;&lt; ia[3] &lt;&lt; endl;
        copy(ia, ia + 10, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        nth_element(ia, ia + 5, ia + 10, greater&lt;int&gt;());

        cout &lt;&lt; "sorting with respect to " &lt;&lt; ia[5] &lt;&lt; endl;
        copy(ia, ia + 10, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        sorting with respect to 4
        1 2 3 4 9 7 5 6 8 10
        sorting with respect to 5
        10 8 7 9 6 5 3 4 2 1
    */
</pre>
    </ul>
<p>
<a name="PARTSORT"></a><a name="l281"></a>
<h3>17.4.34: partial_sort()</h3>
    <a name="stl/partialsort"></a>    <a name="an2461"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,</code>
                <code>RandomAccessIterator last);</code>
            <li><code>void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,</code>
            <code>RandomAccessIterator last, Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the <code>middle - first</code> smallest elements
are sorted and stored in the <code>[first, middle)</code>, using the <a name="an2462"></a>
<code>operator&lt;()</code>
of the data type to which the iterators point. The remaining elements of the
series remain unsorted, and are stored in <code>[middle, last)</code>.
            <li> The second prototype: the <code>middle - first</code> smallest
elements (according to the provided binary predicate <code>comp</code>) are sorted and
stored in the <code>[first, middle)</code>. The remaining elements of the series
remain unsorted.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;functional&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        int ia[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};

        partial_sort(ia, ia + 3, ia + 10);

        cout &lt;&lt; "find the 3 smallest elements:\n";
        copy(ia, ia + 10, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        cout &lt;&lt; "find the 5 biggest elements:\n";
        partial_sort(ia, ia + 5, ia + 10, greater&lt;int&gt;());
        copy(ia, ia + 10, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        find the 3 smallest elements:
        1 2 3 7 9 5 4 6 8 10
        find the 5 biggest elements:
        10 9 8 7 6 1 2 3 4 5
    */
</pre>
    </ul>
<p>
<a name="PARTSORTCP"></a><a name="l282"></a>
<h3>17.4.35: partial_sort_copy()</h3>
    <a name="stl/partialsortcopy"></a>    <a name="an2463"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>void partial_sort_copy(InputIterator first,
                InputIterator last,</code>
                <code>RandomAccessIterator dest_first, RandomAccessIterator
                    dest_last);</code>
            <li><code>void partial_sort_copy(InputIterator first,
                InputIterator last,</code>
          <code>RandomAccessIterator dest_first, RandomAccessIterator dest_last,
            Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the smallest elements in the range
<code>[first, last)</code> are copied to the range <code>[dest_first, dest_last)</code>,
using the <a name="an2464"></a>
<code>operator&lt;()</code> of the data type to which the iterators point. Only
the number of elements in the smaller range are copied to the second range.
            <li> The second prototype: the elements in the range
<code>[first, last)</code> are are sorted by the binary predicate <code>comp</code>. The
elements for which the predicate returns most often <code>true</code> are copied to the
range <code>[dest_first, dest_last)</code>.  Only the number of elements in the
smaller range are copied to the second range.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;functional&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        int ia[] = {1, 10, 3, 8, 5, 6, 7, 4, 9, 2};
        int ia2[6];

        partial_sort_copy(ia, ia + 10, ia2, ia2 + 6);

        copy(ia, ia + 10, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;
        cout &lt;&lt; "the 6 smallest elements: ";
        copy(ia2, ia2 + 6, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        cout &lt;&lt; "the 4 smallest elements to a larger range:\n";
        partial_sort_copy(ia, ia + 4, ia2, ia2 + 6);
        copy(ia2, ia2 + 6, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        cout &lt;&lt; "the 4 biggest elements to a larger range:\n";
        partial_sort_copy(ia, ia + 4, ia2, ia2 + 6, greater&lt;int&gt;());
        copy(ia2, ia2 + 6, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        1 10 3 8 5 6 7 4 9 2
        the 6 smallest elements: 1 2 3 4 5 6
        the 4 smallest elements to a larger range:
        1 3 8 10 5 6
        the 4 biggest elements to a larger range:
        10 8 3 1 5 6
    */
</pre>
    </ul>
<p>
<a name="PARTSUM"></a><a name="l283"></a>
<h3>17.4.36: partial_sum()</h3>
    <a name="stl/partialsum"></a>    <a name="an2465"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;numeric&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>OutputIterator partial_sum(InputIterator first,
InputIterator last,</code><code>OutputIterator result);</code>
            <li><code>OutputIterator partial_sum(InputIterator first,
InputIterator last,</code><code>OutputIterator result, BinaryOperation
op);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: each element in the range
<code>[result, &lt;returned OutputIterator&gt;)</code> receives a value which is obtained
by adding the elements in the corresponding range of the range <code>[first,
last)</code>. The first element in the resulting range will be equal to the element
pointed to by <code>first</code>.
            <li> The second prototype: the value of each element in the range
<code>[result, &lt;returned OutputIterator&gt;)</code> is obtained by applying the binary
operator <code>op</code> to the previous element in the resulting range and the
corresponding element in the range <code>[first, last)</code>. The first
element in the resulting range will be equal to the element pointed to by
<code>first</code>.
        </ul>
        <li> Example:
        <pre>
    #include &lt;numeric&gt;
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;functional&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        int ia[] = {1, 2, 3, 4, 5};
        int ia2[5];

        copy(ia2,
            partial_sum(ia, ia + 5, ia2),
            ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        copy(ia2,
            partial_sum(ia, ia + 5, ia2, multiplies&lt;int&gt;()),
            ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        1 3 6 10 15
        1 2 6 24 120
    */
</pre>
    </ul>
<p>
<a name="PARTIT"></a><a name="l284"></a>
<h3>17.4.37: partition()</h3>
    <a name="stl/partition"></a>    <a name="an2466"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>BidirectionalIterator partition(BidirectionalIterator
first,</code><code>BidirectionalIterator last, UnaryPredicate pred);</code>
        </ul>
        <li> Description:
        <ul>
            <li> All elements in the range <code>[first, last)</code> for which the
unary predicate <code>pred</code> evaluates as <code>true</code> are placed before the elements
which evaluate as <code>false</code>. The return value points just beyond the last
element in the partitioned range for which <code>pred</code> evaluates as <code>true</code>.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;

    class LessThan
    {
        int d_x;
        public:
            LessThan(int x)
            :
                d_x(x)
            {}
            bool operator()(int value)
            {
                return value &lt;= d_x;
            }
    };

    using namespace std;

    int main()
    {
        int ia[] = {1, 3, 5, 7, 9, 10, 2, 8, 6, 4};
        int *split;

        split = partition(ia, ia + 10, LessThan(ia[9]));
        cout &lt;&lt; "Last element &lt;= 4 is ia[" &lt;&lt; split - ia - 1 &lt;&lt; "]\n";

        copy(ia, ia + 10, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        Last element &lt;= 4 is ia[3]
        1 3 4 2 9 10 7 8 6 5
    */
</pre>
    </ul>
<p>
<a name="PREVPERM"></a><a name="l285"></a>
<h3>17.4.38: prev_permutation()</h3>
    <a name="stl/prevpermutation"></a>    <a name="an2467"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>bool prev_permutation(BidirectionalIterator first,
                BidirectionalIterator last);</code>
            <li><code>bool prev_permutation(BidirectionalIterator first,
                BidirectionalIterator</code><code>last, Comp comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the previous permutation given the
sequence of elements in the range <code>[first, last)</code> is determined. The
elements in the range are reordered such that the first ordering is obtained
representing a `smaller' value (see <code>next_permutation()</code> (section
<a href="cplusplus17.html#NEXTPERM">17.4.32</a>) for an example involving the opposite ordering). The value
<code>true</code> is returned if a reordering took place, the value <code>false</code> is
returned if no reordering took place, which is the case if the provided
sequence was already ordered, according to the <a name="an2468"></a>
<code>operator&lt;()</code> of the data
type to which the iterators point.
            <li> The second prototype: the previous permutation given the
sequence of elements in the range <code>[first, last)</code> is determined. The
elements in the range are reordered. The value <code>true</code> is returned if a
reordering took place, the value <code>false</code> is returned if no reordering took
place, which is the case if the original sequence was already ordered,
using the binary predicate <code>comp</code> to compare two elements.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;

    class CaseString
    {
        public:
            bool operator()(std::string const &amp;first,
                            std::string const &amp;second) const
            {
                return strcasecmp(first.c_str(), second.c_str()) &lt; 0;
            }
    };

    using namespace std;

    int main()
    {
        string  saints[] = {"Oh", "when", "the", "saints"};

        cout &lt;&lt; "All previous permutations of 'Oh when the saints':\n";

        cout &lt;&lt; "Sequences:\n";
        do
        {
            copy(saints, saints + 4, ostream_iterator&lt;string&gt;(cout, " "));
            cout &lt;&lt; endl;
        }
        while (prev_permutation(saints, saints + 4, CaseString()));

        cout &lt;&lt; "After first sorting the sequence:\n";
        sort(saints, saints + 4, CaseString());

        cout &lt;&lt; "Sequences:\n";
        while (prev_permutation(saints, saints + 4, CaseString()))
        {
            copy(saints, saints + 4, ostream_iterator&lt;string&gt;(cout, " "));
            cout &lt;&lt; endl;
        }
        cout &lt;&lt; "No (more) previous permutations\n";

        return 0;
    }
    /*
        Generated output:

        All previous permutations of 'Oh when the saints':
        Sequences:
        Oh when the saints
        Oh when saints the
        Oh the when saints
        Oh the saints when
        Oh saints when the
        Oh saints the when
        After first sorting the sequence:
        Sequences:
        No (more) previous permutations
    */
</pre>
    </ul>
<p>
<a name="SHUFFLE"></a><a name="l286"></a>
<h3>17.4.39: random_shuffle()</h3>
    <a name="stl/randomshuffle"></a>    <a name="an2469"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>void random_shuffle(RandomAccessIterator first,
                                    RandomAccessIterator last);</code>
            <li><code>void random_shuffle(RandomAccessIterator first,
                    RandomAccessIterator last,</code>
                    <code>RandomNumberGenerator rand);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the elements in the range <code>[first,
last)</code> are randomly reordered.
            <li> The second prototype:  The elements in the range
<code>[first, last)</code> are randomly reordered, using the <code>rand</code>
    <a name="an2470"></a>
random number generator, which should return an <code>int</code> in the range
<code>[0, remaining)</code>, where <code>remaining</code> is passed as argument to the
<a name="an2471"></a>
<code>operator()()</code> of the <code>rand</code> function object. Alternatively, the random
number generator may be a function expecting an <code>int remaining</code> parameter
and returning an <code>int</code> randomvalue in the range <code>[0, remaining)</code>.  Note
that when a function object is used, it cannot be an anonymous object. The
function in the example uses a procedure outlined in <em>Press et al.</em> (1992)
    <a name="an2472"></a>
 <a name="an2473"></a>
 <strong>Numerical Recipes in C: The
Art of Scientific Computing</strong> (New York: Cambridge University Press, (2nd ed.,
p. 277)).
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;time.h&gt;
    #include &lt;iterator&gt;

    int randomValue(int remaining)
    {
        return static_cast&lt;int&gt;
                ( ((0.0 + remaining) * rand()) / (RAND_MAX + 1.0) );
    }

    class RandomGenerator
    {
        public:
            RandomGenerator()
            {
                srand(time(0));
            }
            int operator()(int remaining) const
            {
                return randomValue(remaining);
            }
    };


    void show(std::string *begin, std::string *end)
    {
        std::copy(begin, end,
                        std::ostream_iterator&lt;std::string&gt;(std::cout, " "));
        std::cout &lt;&lt; std::endl &lt;&lt; std::endl;
    }

    using namespace std;

    int main()
    {
        string words[] =
                    { "kilo", "lima", "mike", "november", "oscar", "papa"};
        size_t const size = sizeof(words) / sizeof(string);

        cout &lt;&lt; "Using Default Shuffle:\n";
        random_shuffle(words, words + size);
        show(words, words + size);

        cout &lt;&lt; "Using RandomGenerator:\n";
        RandomGenerator rg;
        random_shuffle(words, words + size, rg);
        show(words, words + size);

        srand(time(0) &lt;&lt; 1);
        cout &lt;&lt; "Using the randomValue() function:\n";
        random_shuffle(words, words + size, randomValue);
        show(words, words + size);

        return 0;
    }
    /*
        Generated output (for example):

        Using Default Shuffle:
        lima oscar mike november papa kilo

        Using RandomGenerator:
        kilo lima papa oscar mike november

        Using the randomValue() function:
        mike papa november kilo oscar lima
    */
</pre>
    </ul>
<p>
<a name="REMOVE"></a><a name="l287"></a>
<h3>17.4.40: remove()</h3>
    <a name="stl/remove"></a>    <a name="an2474"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>ForwardIterator remove(ForwardIterator first,
ForwardIterator last,</code><code>Type const &amp;value);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The elements in the range pointed to by <code>[first, last)</code>
are reordered in such a way that all values unequal to <code>value</code> are placed at
the beginning of the range. The returned forward iterator points to the first
element that can be removed after reordering. The range <code>[returnvalue,
last)</code> is called the <a name="an2475"></a>
<em>leftover</em> of the algorithm. Note that the leftover may
contain elements different from <code>value</code>, but these elements can be removed
safely, as such elements will also be present in the range <code>[first,
return value)</code>. Such duplication is the result of the fact that the algorithm
<em>copies</em>, rather than <em>moves</em> elements into new locations.  The function
uses <code>operator==()</code> of the data type to which the iterators point to
determine which elements to remove.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        string words[] =
            { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
                "alpha", "alpha", "papa", "quebec" };
        string *removed;
        size_t const size = sizeof(words) / sizeof(string);

        cout &lt;&lt; "Removing all \"alpha\"s:\n";
        removed = remove(words, words + size, "alpha");
        copy(words, removed, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl
             &lt;&lt; "Leftover elements are:\n";
        copy(removed, words + size, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        Removing all "alpha"s:
        kilo lima mike november oscar papa quebec
        Trailing elements are:
        oscar alpha alpha papa quebec
    */
</pre>
    </ul>
<p>
<a name="REMOVECP"></a><a name="l288"></a>
<h3>17.4.41: remove_copy()</h3>
    <a name="stl/removecopy"></a>    <a name="an2476"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>OutputIterator remove_copy(InputIterator first,
                InputIterator last,</code>
                <code>OutputIterator result, Type const &amp;value);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The elements in the range pointed to by <code>[first, last)</code>
not matching <code>value</code> are copied to the range <code>[result, returnvalue)</code>,
where <code>returnvalue</code> is the value returned by the function. The range
<code>[first, last)</code> is not modified.  The function uses <code>operator==()</code> of
the data type to which the iterators point to determine which elements not to
copy.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;functional&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        string words[] =
            { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
                "oscar", "alpha", "alpha", "papa", "quebec" };
        size_t const size = sizeof(words) / sizeof(string);
        string remaining
                [
                    size -
                    count_if
                    (
                        words, words + size,
                        bind2nd(equal_to&lt;string&gt;(), string("alpha"))
                    )
                ];
        string *returnvalue =
                remove_copy(words, words + size, remaining, "alpha");

        cout &lt;&lt; "Removing all \"alpha\"s:\n";
        copy(remaining, returnvalue, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        Removing all "alpha"s:
        kilo lima mike november oscar papa quebec
    */
</pre>
    </ul>
<p>
<a name="REMOVECPIF"></a><a name="l289"></a>
<h3>17.4.42: remove_copy_if()</h3>
    <a name="stl/removecopyif"></a>    <a name="an2477"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>OutputIterator remove_copy_if(InputIterator first,
InputIterator last,</code>
                <code>OutputIterator result, UnaryPredicate pred);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The elements in the range pointed to by <code>[first, last)</code>
for which the unary predicate <code>pred</code> returns <code>true</code> are copied to the
range <code>[result, returnvalue)</code>, where <code>returnvalue</code> is the value
returned by the function. The range <code>[first, last)</code> is not modified.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;functional&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        string words[] =
            { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
                "oscar", "alpha", "alpha", "papa", "quebec" };
        size_t const size = sizeof(words) / sizeof(string);
        string remaining[
                            size -
                            count_if
                            (
                                words, words + size,
                                bind2nd(equal_to&lt;string&gt;(), "alpha")
                            )
                        ];
        string *returnvalue =
                    remove_copy_if
                    (
                        words, words + size, remaining,
                        bind2nd(equal_to&lt;string&gt;(), "alpha")
                    );

        cout &lt;&lt; "Removing all \"alpha\"s:\n";
        copy(remaining, returnvalue, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        Removing all "alpha"s:
        kilo lima mike november oscar papa quebec
    */
</pre>
    </ul>
<p>
<a name="REMOVEIF"></a><a name="l290"></a>
<h3>17.4.43: remove_if()</h3>
    <a name="stl/removeif"></a>    <a name="an2478"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>ForwardIterator remove_if(ForwardIterator first,
ForwardIterator last,</code><code>UnaryPredicate pred);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The elements in the range pointed to by <code>[first, last)</code>
are reordered in such a way that all values for which the unary predicate
<code>pred</code> evaluates as <code>false</code> are placed at the beginning of the range. The
returned forward iterator points to the first element, after reordering, for
which <code>pred</code> returns <code>true</code>. The range <code>[returnvalue, last)</code> is
called the <em>leftover</em> of the algorithm. The leftover may contain elements
for which the predicate <code>pred</code> returns <code>false</code>, but these can safely
be removed, as such elements will  also be present in the range <code>[first,
returnvalue)</code>. Such duplication is the result of the fact that the algorithm
<em>copies</em>, rather than <em>moves</em> elements into new locations.
        </ul>
        <li> Example:<pre>
    #include &lt;functional&gt;
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        string words[] =
            { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
                "oscar", "alpha", "alpha", "papa", "quebec" };
        size_t const size = sizeof(words) / sizeof(string);

        cout &lt;&lt; "Removing all \"alpha\"s:\n";

        string *removed = remove_if(words, words + size,
                    bind2nd(equal_to&lt;string&gt;(), string("alpha")));

        copy(words, removed, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl
             &lt;&lt; "Trailing elements are:\n";
        copy(removed, words + size, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        Removing all "alpha"s:
        kilo lima mike november oscar papa quebec
        Trailing elements are:
        oscar alpha alpha papa quebec
    */
</pre>
    </ul>
<p>
<a name="REPLACE"></a><a name="l291"></a>
<h3>17.4.44: replace()</h3>
    <a name="stl/replace"></a>    <a name="an2479"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>ForwardIterator replace(ForwardIterator first,
ForwardIterator last,</code>
        <code>Type const &amp;oldvalue, Type const &amp;newvalue);</code>
        </ul>
        <li> Description:
        <ul>
            <li> All elements equal to <code>oldvalue</code> in the range pointed to by
<code>[first, last)</code> are replaced by a copy of <code>newvalue</code>. The algorithm
uses <code>operator==()</code> of the data type to which the iterators point.
<p>
</ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        string words[] =
            { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
                "oscar", "alpha", "alpha", "papa", "quebec" };
        size_t const size = sizeof(words) / sizeof(string);

        replace(words, words + size, string("alpha"), string("ALPHA"));
        copy(words, words + size, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        kilo ALPHA lima mike ALPHA november ALPHA oscar ALPHA ALPHA papa quebec
    */
</pre>
    </ul>
<p>
<a name="REPLACECP"></a><a name="l292"></a>
<h3>17.4.45: replace_copy()</h3>
    <a name="stl/replacecopy"></a>    <a name="an2480"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>OutputIterator replace_copy(InputIterator first,
InputIterator last,</code>
    <code>OutputIterator result, Type const &amp;oldvalue,
                              Type const &amp;newvalue);</code>
        </ul>
        <li> Description:
        <ul>
            <li> All elements equal to <code>oldvalue</code> in the range pointed to by
<code>[first, last)</code> are replaced by a copy of <code>newvalue</code> in a new range
<code>[result, returnvalue)</code>, where <code>returnvalue</code> is the return value of the
function.  The algorithm uses <code>operator==()</code> of the data type to which the
iterators point.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        string words[] =
            { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
                "oscar", "alpha", "alpha", "papa", "quebec" };
        size_t const size = sizeof(words) / sizeof(string);
        string remaining[size];

        copy
        (
            remaining,
            replace_copy(words, words + size, remaining, string("alpha"),
                                                         string("ALPHA")),
            ostream_iterator&lt;string&gt;(cout, " ")
        );
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        kilo ALPHA lima mike ALPHA november ALPHA oscar ALPHA ALPHA papa quebec
    */
</pre>
    </ul>
<p>
<a name="REPLACECPIF"></a><a name="l293"></a>
<h3>17.4.46: replace_copy_if()</h3>
    <a name="stl/replacecopyif"></a>    <a name="an2481"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>OutputIterator replace_copy_if(ForwardIterator first,
ForwardIterator</code>  <code>last, OutputIterator result, UnaryPredicate
pred, Type const &amp;value);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The elements in the range pointed to by <code>[first, last)</code>
are copied to the range <code>[result, returnvalue)</code>, where <code>returnvalue</code> is
the value returned by the function. The elements for which the unary predicate
<code>pred</code> returns <code>true</code> are replaced by <code>newvalue</code>. The range
<code>[first, last)</code> is not modified.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;functional&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        string words[] =
            { "kilo", "alpha", "lima", "mike", "alpha", "november",
              "alpha", "oscar", "alpha", "alpha", "papa", "quebec" };
        size_t const size = sizeof(words) / sizeof(string);
        string result[size];

        replace_copy_if(words, words + size, result,
                        bind1st(greater&lt;string&gt;(), string("mike")),
                        string("ALPHA"));
        copy (result, result + size, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output (all on one line):

        ALPHA ALPHA ALPHA mike ALPHA november ALPHA oscar ALPHA ALPHA
                                                          papa quebec
    */
</pre>
    </ul>
<p>
<a name="REPLACEIF"></a><a name="l294"></a>
<h3>17.4.47: replace_if()</h3>
    <a name="stl/replaceif"></a>    <a name="an2482"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>ForwardIterator replace_if(ForwardIterator first,
ForwardIterator last,</code>
            <code>UnaryPredicate pred, Type const &amp;value);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The elements in the range pointed to by <code>[first, last)</code>
for which the unary predicate <code>pred</code> evaluates as <code>true</code>
are replaced by <code>newvalue</code>.
        </ul>
        <code></code> Example:<pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;functional&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        string words[] =
            { "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
                "oscar", "alpha", "alpha", "papa", "quebec" };
        size_t const size = sizeof(words) / sizeof(string);

        replace_if(words, words + size,
                   bind1st(equal_to&lt;string&gt;(), string("alpha")),
                   string("ALPHA"));
        copy(words, words + size, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;
    }
    /*
        generated output:

        kilo ALPHA lima mike ALPHA november ALPHA oscar ALPHA ALPHA papa quebec
    */
</pre>
    </ul>
<p>
<a name="REVERSE"></a><a name="l295"></a>
<h3>17.4.48: reverse()</h3>
    <a name="stl/reverse"></a><a name="an2483"></a>

<ul>
    <li> Header file:
    <pre>
        #include &lt;algorithm&gt;
</pre>
    <li> Function prototype:
    <ul>
        <li><code>void reverse(BidirectionalIterator first,
            BidirectionalIterator last);</code>
    </ul>
    <li> Description:
    <ul>
        <li> The elements in the range pointed to by <code>[first, last)</code>
are reversed.
    </ul>
    <li> Example:
    <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    using namespace std;

    int main()
    {
        string line;

        while (getline(cin, line))
        {
            reverse(line.begin(), line.end());
            cout &lt;&lt; line &lt;&lt; endl;
        }

        return 0;
    }
</pre>
</ul>
<p>
<a name="REVERSECP"></a><a name="l296"></a>
<h3>17.4.49: reverse_copy()</h3>
    <a name="stl/reversecopy"></a><a name="an2484"></a>

<ul>
    <li> Header file:
    <pre>
        #include &lt;algorithm&gt;
</pre>
    <li> Function prototype:
    <ul>
        <li><code>OutputIterator reverse_copy(BidirectionalIterator first,</code>
            
            <code>BidirectionalIterator last, OutputIterator result);</code>
    </ul>
    <li> Description:
    <ul>
        <li> The elements in the range pointed to by <code>[first, last)</code>
are copied to the range <code>[result, returnvalue)</code> in reversed order. The
value <code>returnvalue</code> is the value that is returned by the function.
    </ul>
    <li> Example:
    <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    using namespace std;

    int main()
    {
        string line;

        while (getline(cin, line))
        {
            size_t    size = line.size();
            char        copy[size + 1];

            cout &lt;&lt; "line: " &lt;&lt; line &lt;&lt; endl &lt;&lt;
                    "reversed: ";
            reverse_copy(line.begin(), line.end(), copy);
            copy[size] = 0;     // 0 is not part of the reversed
                                // line !
            cout &lt;&lt; copy &lt;&lt; endl;
        }
        return 0;
    }
</pre>
</ul>
<p>
<a name="ROTATE"></a><a name="l297"></a>
<h3>17.4.50: rotate()</h3>
    <a name="stl/rotate"></a><a name="an2485"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>void rotate(ForwardIterator first, ForwardIterator
middle, ForwardIterator</code><code>last);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The elements implied by the range <code>[first, middle)</code> are
moved to the end of the container, the elements implied by the range
<code>[middle, last)</code> are moved to the beginning of the container, keeping the
order of the elements in the two subsets intact.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        string words[] =
            { "kilo", "lima", "mike", "november", "oscar", "papa",
              "echo", "foxtrot", "golf", "hotel", "india", "juliet" };
        size_t const size = sizeof(words) / sizeof(string);
        size_t const midsize = 6;

        rotate(words, words + midsize, words + size);

        copy(words, words + size, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        echo foxtrot golf hotel india juliet kilo lima mike november oscar papa
    */
</pre>
    </ul>
<p>
<a name="ROTATECP"></a><a name="l298"></a>
<h3>17.4.51: rotate_copy()</h3>
    <a name="stl/rotatecopy"></a><a name="an2486"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>OutputIterator rotate_copy(ForwardIterator first,
ForwardIterator middle,</code>
                <code>ForwardIterator last, OutputIterator result);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The elements implied by the range <code>[middle, last)</code> and
then the elements implied by the range <code>[first, middle)</code> are copied to the
destination container having range <code>[result, returnvalue)</code>, where
<code>returnvalue</code> is the iterator returned by the function. The original order
of the elements in the two subsets is not altered.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        string words[] =
            { "kilo", "lima", "mike", "november", "oscar", "papa",
              "echo", "foxtrot", "golf", "hotel", "india", "juliet" };
        size_t const size = sizeof(words) / sizeof(string);
        size_t midsize = 6;
        string out[size];

        copy(out,
            rotate_copy(words, words + midsize, words + size, out),
            ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        echo foxtrot golf hotel india juliet kilo lima mike november oscar papa
    */
</pre>
    </ul>
<p>
<a name="SEARCH"></a><a name="l299"></a>
<h3>17.4.52: search()</h3>
    <a name="stl/search"></a><a name="an2487"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>ForwardIterator1 search(ForwardIterator1 first1,
ForwardIterator1 last1,</code>
                <code>ForwardIterator2 first2, ForwardIterator2 last2);</code>
            <li><code>ForwardIterator1 search(ForwardIterator1 first1,
ForwardIterator1 last1,</code>
            <code>ForwardIterator2 first2, ForwardIterator2 last2,
                BinaryPredicate pred);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: an iterator into the first range
<code>[first1, last1)</code> is returned where the elements in the range
<code>[first2, last2)</code> are found, using <a name="an2488"></a>
<code>operator==()</code> operator of the data
type to which the iterators point. If no such location exists, <code>last1</code> is
returned.
            <li> The second prototype: an iterator into the first range
<code>[first1, last1)</code> is returned where the elements in the range
<code>[first2, last2)</code> are found, using the provided binary predicate <code>pred</code>
to compare the elements in the two ranges. If no such location exists,
<code>last1</code> is returned.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;iterator&gt;

    class absInt
    {
        public:
            bool operator()(int i1, int i2)
            {
                return abs(i1) == abs(i2);
            }
    };

    using namespace std;

    int main()
    {
        int range1[] =  {-2, -4, -6, -8, 2, 4, 6, 8};
        int range2[] =  {6, 8};

        copy
        (
            search(range1, range1 + 8, range2, range2 + 2),
            range1 + 8,
            ostream_iterator&lt;int&gt;(cout, " ")
        );
        cout &lt;&lt; endl;

        copy
        (
            search(range1, range1 + 8, range2, range2 + 2, absInt()),
            range1 + 8,
            ostream_iterator&lt;int&gt;(cout, " ")
        );
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        6 8
        -6 -8 2 4 6 8
    */
</pre>
    </ul>
<p>
<a name="SEARCHN"></a><a name="l300"></a>
<h3>17.4.53: search_n()</h3>
    <a name="stl/searchn"></a><a name="an2489"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>ForwardIterator1 search_n(ForwardIterator1 first1,
ForwardIterator1 last1, Size count, Type const &amp;value);</code>
            <li><code>ForwardIterator1 search_n(ForwardIterator1 first1,
ForwardIterator1 last1, Size count, Type const &amp;value, BinaryPredicate
pred);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: an iterator into the first range
<code>[first1, last1)</code> is returned where <code>n</code> elements having value <code>value</code>
are found, using <a name="an2490"></a>
<code>operator==()</code> of the data type to which the iterators
point to compare the elements. If no such location exists, <code>last1</code> is
returned.
            <li> The second prototype: an iterator into the first range
<code>[first1, last1)</code> is returned where <code>n</code> elements having value <code>value</code>
are found, using the provided binary predicate <code>pred</code> to compare the
elements. If no such location exists, <code>last1</code> is returned.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;iterator&gt;

    class absInt
    {
        public:
            bool operator()(int i1, int i2)
            {
                return abs(i1) == abs(i2);
            }
    };

    using namespace std;

    int main()
    {
        int range1[] =  {-2, -4, -4, -6, -8, 2, 4, 4, 6, 8};
        int range2[] =  {6, 8};

        copy
        (
            search_n(range1, range1 + 8, 2, 4),
            range1 + 8,
            ostream_iterator&lt;int&gt;(cout, " ")
        );
        cout &lt;&lt; endl;

        copy
        (
            search_n(range1, range1 + 8, 2, 4, absInt()),
            range1 + 8,
            ostream_iterator&lt;int&gt;(cout, " ")
        );
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        4 4
        -4 -4 -6 -8 2 4 4
    */
</pre>
    </ul>
<p>
<a name="SETDIF"></a><a name="l301"></a>
<h3>17.4.54: set_difference()</h3>
    <a name="stl/setdifference"></a><a name="an2491"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>OutputIterator set_difference(InputIterator1
                    first1, InputIterator1 last1,</code>
                <code>InputIterator2 first2, InputIterator2 last2,
                OutputIterator result);</code>
            <li><code>OutputIterator set_difference(InputIterator1
                    first1, InputIterator1 last1,</code>
                <code>InputIterator2 first2, InputIterator2 last2,
                OutputIterator result,</code>
                <code>Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: a sorted sequence of the elements
pointed to by the range <code>[first1, last1)</code> that are not present in the
range <code>[first2, last2)</code> is returned, starting at <code>result</code>, and ending
at the <code>OutputIterator</code> returned by the function. The elements in the two
ranges must have been sorted using <a name="an2492"></a>
<code>operator&lt;()</code> of the data type to which
the iterators point.
            <li> The second prototype: a sorted sequence of the elements
pointed to by the range <code>[first1, last1)</code> that are not present in the
range <code>[first2, last2)</code> is returned, starting at <code>result</code>, and ending
at the <code>OutputIterator</code> returned by the function. The elements in the two
ranges must have been sorted using the <code>comp</code> function object.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;

    class CaseLess
    {
        public:
            bool operator()(std::string const &amp;left, std::string const &amp;right)
            {
                return strcasecmp(left.c_str(), right.c_str()) &lt; 0;
            }
    };

    using namespace std;

    int main()
    {
        string set1[] = { "kilo", "lima", "mike", "november",
                          "oscar", "papa", "quebec" };
        string set2[] = { "papa", "quebec", "romeo"};
        string result[7];
        string *returned;

        copy(result,
            set_difference(set1, set1 + 7, set2, set2 + 3, result),
            ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        string set3[] = { "PAPA", "QUEBEC", "ROMEO"};

        copy(result,
            set_difference(set1, set1 + 7, set3, set3 + 3, result,
            CaseLess()),
            ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        kilo lima mike november oscar
        kilo lima mike november oscar
    */
</pre>
    </ul>
<p>
<a name="SETINT"></a><a name="l302"></a>
<h3>17.4.55: set_intersection()</h3>
    <a name="stl/setintersection"></a><a name="an2493"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>OutputIterator set_intersection(InputIterator1 first1,
InputIterator1</code>  <code>last1, InputIterator2 first2, InputIterator2
last2, OutputIterator</code>  <code>result);</code>
            <li><code>OutputIterator set_intersection(InputIterator1 first1,
InputIterator1</code>  <code>last1, InputIterator2 first2, InputIterator2
last2, OutputIterator</code>  <code>result, Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: a sorted sequence of the elements
pointed to by the range <code>[first1, last1)</code> that are also present in the
range <code>[first2, last2)</code> is returned, starting at <code>result</code>, and ending
at the <code>OutputIterator</code> returned by the function. The elements in the two
ranges must have been sorted using <a name="an2494"></a>
<code>operator&lt;()</code> of the data type to which
the iterators point.
            <li> The second prototype: a sorted sequence of the elements
pointed to by the range <code>[first1, last1)</code> that are also present in the
range <code>[first2, last2)</code> is returned, starting at <code>result</code>, and ending
at the <code>OutputIterator</code> returned by the function. The elements in the two
ranges must have been sorted using the <code>comp</code> function object.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;

    class CaseLess
    {
        public:
            bool operator()(std::string const &amp;left, std::string const &amp;right)
            {
                return strcasecmp(left.c_str(), right.c_str()) &lt; 0;
            }
    };

    using namespace std;

    int main()
    {
        string set1[] = { "kilo", "lima", "mike", "november",
                          "oscar", "papa", "quebec" };
        string set2[] = { "papa", "quebec", "romeo"};
        string result[7];
        string *returned;

        copy(result,
            set_intersection(set1, set1 + 7, set2, set2 + 3, result),
            ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        string set3[] = { "PAPA", "QUEBEC", "ROMEO"};

        copy(result,
            set_intersection(set1, set1 + 7, set3, set3 + 3, result,
            CaseLess()),
            ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        papa quebec
        papa quebec
    */
</pre>
    </ul>
<p>
<a name="SETSYM"></a><a name="l303"></a>
<h3>17.4.56: set_symmetric_difference()</h3>
    <a name="stl/setsymmetricdifference"></a><a name="an2495"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>OutputIterator set_symmetric_difference(
                InputIterator1 first1,</code>
                <code>InputIterator1 last1, InputIterator2 first2,</code>
                <code>InputIterator2 last2, OutputIterator result);</code>
            <li><code>OutputIterator set_symmetric_difference(
                InputIterator1 first1,</code>
                <code>InputIterator1 last1, InputIterator2 first2,</code>
                <code>InputIterator2 last2, OutputIterator result,</code>
                <code>Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: a sorted sequence of the elements
pointed to by the range <code>[first1, last1)</code> that are not present in the
range <code>[first2, last2)</code> and those in the range <code>[first2, last2)</code>
that are not present in the range <code>[first1, last1)</code> is returned, starting
at <code>result</code>, and ending at the <code>OutputIterator</code> returned by the
function. The elements in the two ranges must have been sorted using
<a name="an2496"></a>
<code>operator&lt;()</code> of the data type to which the iterators point.
            <li> The second prototype: a sorted sequence of the elements
pointed to by the range <code>[first1, last1)</code> that are not present in the
range <code>[first2, last2)</code> and those in the range <code>[first2, last2)</code>
that are not present in the range <code>[first1, last1)</code> is returned, starting
at <code>result</code>, and ending at the <code>OutputIterator</code> returned by the
function. The elements in the two ranges must have been sorted using the
<code>comp</code> function object.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;

    class CaseLess
    {
        public:
            bool operator()(std::string const &amp;left, std::string const &amp;right)
            {
                return strcasecmp(left.c_str(), right.c_str()) &lt; 0;
            }
    };

    using namespace std;

    int main()
    {
        string set1[] = { "kilo", "lima", "mike", "november",
                          "oscar", "papa", "quebec" };
        string set2[] = { "papa", "quebec", "romeo"};
        string result[7];
        string *returned;

        copy(result,
            set_symmetric_difference(set1, set1 + 7, set2, set2 + 3,
                                                           result),
            ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        string set3[] = { "PAPA", "QUEBEC", "ROMEO"};

        copy(result,
            set_symmetric_difference(set1, set1 + 7, set3, set3 + 3,
                                                           result,
            CaseLess()),
            ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        kilo lima mike november oscar romeo
        kilo lima mike november oscar ROMEO
    */
</pre>
    </ul>
<p>
<a name="SETUNI"></a><a name="l304"></a>
<h3>17.4.57: set_union()</h3>
    <a name="stl/setunion"></a><a name="an2497"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>OutputIterator set_union(InputIterator1 first1,
                InputIterator1 last1,</code>
                <code>InputIterator2 first2, InputIterator2 last2,
                OutputIterator result);</code>
            <li><code>OutputIterator set_union(InputIterator1 first1,
                InputIterator1 last1,</code>
                <code>InputIterator2 first2, InputIterator2 last2,
                OutputIterator result,</code>
                <code>Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: a sorted sequence of the elements that
are present in either the range <code>[first1, last1)</code> or the range
<code>[first2, last2)</code> or in both ranges is returned, starting at <code>result</code>,
and ending at the <code>OutputIterator</code> returned by the function. The elements in
the two ranges must have been sorted using <a name="an2498"></a>
<code>operator&lt;()</code> of the data type to
which the iterators point. Note that in the final range each element will
appear only once.
            <li> The second prototype: a sorted sequence of the elements that
are present in either the range <code>[first1, last1)</code> or the range
<code>[first2, last2)</code> or in both ranges is returned, starting at <code>result</code>,
and ending at the <code>OutputIterator</code> returned by the function. The elements in
the two ranges must have been sorted using <code>comp</code> function object. Note that
in the final range each element will appear only once.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;

    class CaseLess
    {
        public:
            bool operator()(std::string const &amp;left, std::string const &amp;right)
            {
                return strcasecmp(left.c_str(), right.c_str()) &lt; 0;
            }
    };

    using namespace std;

    int main()
    {
        string set1[] = { "kilo", "lima", "mike", "november",
                          "oscar", "papa", "quebec" };
        string set2[] = { "papa", "quebec", "romeo"};
        string result[7];
        string *returned;

        copy(result,
            set_union(set1, set1 + 7, set2, set2 + 3, result),
            ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        string set3[] = { "PAPA", "QUEBEC", "ROMEO"};

        copy(result,
            set_union(set1, set1 + 7, set3, set3 + 3, result,
            CaseLess()),
            ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        kilo lima mike november oscar papa quebec romeo
        kilo lima mike november oscar papa quebec ROMEO
    */
</pre>
    </ul>
<p>
<a name="SORT"></a><a name="l305"></a>
<h3>17.4.58: sort()</h3>
    <a name="stl/sort"></a><a name="an2499"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>void sort(RandomAccessIterator first,
                RandomAccessIterator last);</code>
            <li><code>void sort(RandomAccessIterator first,
                RandomAccessIterator last,</code>
                <code>Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
           <li> The first prototype: the elements in the range <code>[first,
last)</code> are sorted in ascending order, using <a name="an2500"></a>
<code>operator&lt;()</code> of the data type to
which the iterators point.
            <li> The second prototype: the elements in the range
<code>[first, last)</code> are sorted in ascending order, using the <code>comp</code>
function object to compare the elements. The binary predicate <code>comp</code>
should return <code>true</code> if its first argument should be placed earlier in the
sorted sequence than its second argument.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;functional&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        string words[] = {"november", "kilo", "mike", "lima",
                          "oscar", "quebec", "papa"};

        sort(words, words + 7);
        copy(words, words + 7, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        sort(words, words + 7, greater&lt;string&gt;());
        copy(words, words + 7, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        kilo lima mike november oscar papa quebec
        quebec papa oscar november mike lima kilo
    */
</pre>
    </ul>
<p>
<a name="STABPART"></a><a name="l306"></a>
<h3>17.4.59: stable_partition()</h3>
    <a name="stl/stablepartition"></a><a name="an2501"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototype:
        <ul>
            <li><code>BidirectionalIterator
              stable_partition(BidirectionalIterator first,</code>
              <code>BidirectionalIterator last, UnaryPredicate pred);</code>
        </ul>
        <li> Description:
        <ul>
            <li> All elements in the range <code>[first, last)</code> for which the
unary predicate <code>pred</code> evaluates as <code>true</code> are placed before the elements
which evaluate as <code>false</code>. The relative order of equal elements in the
container is kept. The return value points just beyond the last element in the
partitioned range for which <code>pred</code> evaluates as <code>true</code>.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;functional&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        int org[] = {1, 3, 5, 7, 9, 10, 2, 8, 6, 4};
        int ia[10];
        int *split;

        copy(org, org + 10, ia);
        split = partition(ia, ia + 10, bind2nd(less_equal&lt;int&gt;(), ia[9]));
        cout &lt;&lt; "Last element &lt;= 4 is ia[" &lt;&lt; split - ia - 1 &lt;&lt; "]\n";

        copy(ia, ia + 10, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        copy(org, org + 10, ia);
        split = stable_partition(ia, ia + 10,
                                    bind2nd(less_equal&lt;int&gt;(), ia[9]));
        cout &lt;&lt; "Last element &lt;= 4 is ia[" &lt;&lt; split - ia - 1 &lt;&lt; "]\n";

        copy(ia, ia + 10, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        Last element &lt;= 4 is ia[3]
        1 3 4 2 9 10 7 8 6 5
        Last element &lt;= 4 is ia[3]
        1 3 2 4 5 7 9 10 8 6
    */
</pre>
    </ul>
<p>
<a name="STABSORT"></a><a name="l307"></a>
<h3>17.4.60: stable_sort()</h3>
    <a name="stl/stablesort"></a><a name="an2502"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>void stable_sort(RandomAccessIterator first,
                RandomAccessIterator last);</code>
            <li><code>void stable_sort(RandomAccessIterator first,
                RandomAccessIterator last,</code>
                <code>Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
           <li> The first prototype: the elements in the range <code>[first,
last)</code> are stable-sorted in ascending order, using <a name="an2503"></a>
<code>operator&lt;()</code> of the data
type to which the iterators point: the relative order of equal elements is
kept.
            <li> The second prototype: the elements in the range
<code>[first, last)</code> are stable-sorted in ascending order, using the <code>comp</code>
binary predicate to compare the elements. This predicate should return
<code>true</code> if its first argument should be placed before its second argument in
the sorted set of element.
        </ul>
        <li> Example (annotated below):
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;vector&gt;
    #include &lt;iterator&gt;

    typedef std::pair&lt;std::string, std::string&gt;  pss;   // 1 (see the text)

    namespace std
    {
        ostream &amp;operator&lt;&lt;(ostream &amp;out, pss const &amp;p)                 // 2
        {
            return out &lt;&lt; "    " &lt;&lt; p.first &lt;&lt; " " &lt;&lt; p.second &lt;&lt; endl;
        }
    }

    class sortby
    {
        std::string pss::*d_field;
        public:
            sortby(std::string pss::*field)                             // 3
            :
                d_field(field)
            {}

            bool operator()(pss const &amp;p1, pss const &amp;p2) const         // 4
            {
                return p1.*d_field &lt; p2.*d_field;
            }
    };

    using namespace std;

    int main()
    {
        vector&lt;pss&gt; namecity;                                           // 5

        namecity.push_back(pss("Hampson",   "Godalming"));
        namecity.push_back(pss("Moran",     "Eugene"));
        namecity.push_back(pss("Goldberg",  "Eugene"));
        namecity.push_back(pss("Moran",     "Godalming"));
        namecity.push_back(pss("Goldberg",  "Chicago"));
        namecity.push_back(pss("Hampson",   "Eugene"));

        sort(namecity.begin(), namecity.end(), sortby(&amp;pss::first));    // 6

        cout &lt;&lt; "sorted by names:\n";
        copy(namecity.begin(), namecity.end(), ostream_iterator&lt;pss&gt;(cout));

                                                                        // 7
        stable_sort(namecity.begin(), namecity.end(), sortby(&amp;pss::second));

        cout &lt;&lt; "sorted by names within sorted cities:\n";
        copy(namecity.begin(), namecity.end(), ostream_iterator&lt;pss&gt;(cout));

        return 0;
    }
    /*
        Generated output:

        sorted by names:
            Goldberg Eugene
            Goldberg Chicago
            Hampson Godalming
            Hampson Eugene
            Moran Eugene
            Moran Godalming
        sorted by names within sorted cities:
            Goldberg Chicago
            Goldberg Eugene
            Hampson Eugene
            Moran Eugene
            Hampson Godalming
            Moran Godalming
    */
</pre>
    </ul>
    Note that the example implements a solution to an often occurring problem:
how to <a name="an2504"></a>
sort using multiple hierarchical criteria. The example deserves some
additional attention:
    <ol>
    <li> First, a <a name="an2505"></a>
<code>typedef</code> is used to reduce the clutter that occurs from
the repeated use of <code>pair&lt;string, string&gt;</code>.
    <li> Next, <a name="an2506"></a>
 <code>operator</code><<<code>()</code> is overloaded to be able to insert
a <code>pair</code> into an <a name="an2507"></a>
<code>ostream</code> object. This is merely a service function to
make life easy. Note, however, that this function is put in the <code>std</code>
namespace. If this namespace wrapping is omitted, it won't be used, as
<code>ostream</code>'s <code>operator</code><<<code>()</code> operators must be part of the <code>std</code> namespace.
    <li> Then, a class <code>sortby</code> is defined, allowing us to construct an
<a name="an2508"></a>
anonymous object which receives a pointer to one of the <code>pair</code> data
members that are used for sorting. In this case, as both members are
<code>string</code> objects, the constructor can easily be defined: its parameter is a
pointer to a <code>string</code> member of the class <code>pair&lt;string, string&gt;</code>.
    <li> The <code>operator()()</code> member will receive two <code>pair</code> references,
and it will then use the pointer to its members, stored in the <code>sortby</code>
object, to compare the appropriate fields of the <code>pairs</code>.
    <li> In <code>main()</code>, first some data is stored in a <code>vector</code>.
    <li> Then the first sorting takes place. The least important criterion
must be sorted first, and for this a simple <code>sort()</code> will suffice. Since we
want the names to be sorted within cities, the names represent the least
important criterion, so we sort by names: <code>sortby(&amp;pss::first)</code>.
    <li> The next important criterion, the cities, are sorted next. Since the
relative ordering of the <em>names</em> will not be altered anymore by
<code>stable_sort()</code>, the ties that are observed when cities are sorted are
solved in such a way that the existing relative ordering will not be
broken. So, we end up getting Goldberg in Eugene before Hampson in Eugene,
before Moran in Eugene. To sort by cities, we use another anonymous <code>sortby</code>
object: <code>sortby(&amp;pss::second)</code>.
    </ol>
<p>
<a name="SWAP"></a><a name="l308"></a>
<h3>17.4.61: swap()</h3>
    <a name="stl/swap"></a><a name="an2509"></a>

<ul>
    <li> Header file:
    <pre>
        #include &lt;algorithm&gt;
</pre>
    <li> Function prototype:
    <ul>
        <li><code>void swap(Type &amp;object1, Type &amp;object2);</code>
    </ul>
    <li> Description:
    <ul>
        <li> The elements <code>object1</code> and <code>object2</code> exchange their values.
    </ul>
    <li> Example:
    <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        string first[] = {"alpha", "bravo", "charley"};
        string second[] = {"echo", "foxtrot", "golf"};
        size_t const n = sizeof(first) / sizeof(string);

        cout &lt;&lt; "Before:\n";
        copy(first, first + n, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;
        copy(second, second + n, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        for (size_t idx = 0; idx &lt; n; ++idx)
            swap(first[idx], second[idx]);

        cout &lt;&lt; "After:\n";
        copy(first, first + n, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;
        copy(second, second + n, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        Before:
        alpha bravo charley
        echo foxtrot golf
        After:
        echo foxtrot golf
        alpha bravo charley
    */
</pre>
</ul>
<p>
<a name="SWAPRAN"></a><a name="l309"></a>
<h3>17.4.62: swap_ranges()</h3>
    <a name="stl/swapranges"></a><a name="an2510"></a>

<ul>
    <li> Header file:
    <pre>
        #include &lt;algorithm&gt;
</pre>
    <li> Function prototype:
    <ul>
        <li><code>ForwardIterator2 swap_ranges(ForwardIterator1 first1,
            ForwardIterator1</code>
            <code>last1, ForwardIterator2 result);</code>
    </ul>
    <li> Description:
    <ul>
        <li> The elements in the range
pointed to by <code>[first1, last1)</code> are swapped with the elements in the
range <code>[result, returnvalue)</code>, where <code>returnvalue</code> is the value
returned by the function. The two ranges must be disjoint.
    </ul>
    <li> Example:
    <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        string first[] = {"alpha", "bravo", "charley"};
        string second[] = {"echo", "foxtrot", "golf"};
        size_t const n = sizeof(first) / sizeof(string);

        cout &lt;&lt; "Before:\n";
        copy(first, first + n, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;
        copy(second, second + n, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        swap_ranges(first, first + n, second);

        cout &lt;&lt; "After:\n";
        copy(first, first + n, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;
        copy(second, second + n, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        Before:
        alpha bravo charley
        echo foxtrot golf
        After:
        echo foxtrot golf
        alpha bravo charley
    */
</pre>
</ul>
<p>
<a name="TRANSFORM"></a><a name="l310"></a>
<h3>17.4.63: transform()</h3>
    <a name="stl/transform"></a><a name="an2511"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>OutputIterator transform(InputIterator first,
InputIterator last,</code><code>OutputIterator result, UnaryOperator op);</code>
            <li><code>OutputIterator transform(InputIterator1 first1,
                InputIterator1 last1,</code>
                <code>InputIterator2 first2, OutputIterator result,
                    BinaryOperator op);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the unary operator <code>op</code> is applied to
each of the elements in the range <code>[first, last)</code>, and the resulting
values are stored in the range starting at <code>result</code>. The return value points
just beyond the last generated element.
            <li> The second prototype: the binary operator <code>op</code> is applied
to each of the elements in the range <code>[first1, last1)</code> and the
corresponding element in the second range starting at <code>first2</code>. The
resulting values are stored in the range starting at <code>result</code>. The return
value points just beyond the last generated element.
        </ul>
        <li> Example:
        <pre>
    #include &lt;functional&gt;
    #include &lt;vector&gt;
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;cctype&gt;
    #include &lt;iterator&gt;

    class Caps
    {
        public:
            std::string operator()(std::string const &amp;src)
            {
                std::string tmp = src;

                transform(tmp.begin(), tmp.end(), tmp.begin(), toupper);
                return tmp;
            }
    };

    using namespace std;

    int main()
    {
        string words[] = {"alpha", "bravo", "charley"};

        copy(words, transform(words, words + 3, words, Caps()),
                                ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        int         values[] = {1, 2, 3, 4, 5};
        vector&lt;int&gt; squares;

        transform(values, values + 5, values,
                                back_inserter(squares), multiplies&lt;int&gt;());

        copy(squares.begin(), squares.end(),
                                ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        ALPHA BRAVO CHARLEY
        1 4 9 16 25
    */
</pre>
    </ul>
    the following differences between the <code>for_each()</code> (section
<a href="cplusplus17.html#FOREACH">17.4.17</a>) and <code>transform()</code> generic algorithms should be noted:
    <a name="an2512"></a>

    <a name="an2513"></a>

    <ul>
        <li> With <code>transform()</code> the <em>return value</em> of the function
object's <code>operator()()</code> member is used; the argument that is passed to the
<code>operator()()</code> member itself is not changed.
        <li> With <code>for_each()</code> the function object's <code>operator()()</code>
receives a reference to an argument, which itself may be changed by the
function object's <code>operator()()</code>.
    </ul>
<p>
<a name="UNIQUE"></a><a name="l311"></a>
<h3>17.4.64: unique()</h3>
    <a name="stl/unique"></a><a name="an2514"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>ForwardIterator unique(ForwardIterator first,
ForwardIterator last);</code>
            <li><code>ForwardIterator unique(ForwardIterator first,
ForwardIterator last,</code><code>BinaryPredicate pred);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: using <a name="an2515"></a>
<code>operator==()</code>, all but the
first of consecutively equal elements of the data type to which the iterators
point in the range pointed to by <code>[first, last)</code> are relocated to the
end of the range. The returned forward iterator marks the beginning of the
<a name="an2516"></a>
<em>leftover</em>. All elements in the range <code>[first, return-value)</code> are
unique, all elements in the range <code>[return-value, last)</code> are equal to
elements in the range <code>[first, return-value)</code>.
            <li> The second prototype: all but the first of consecutive
elements in the range pointed to by <code>[first, last)</code> for which the binary
predicate <code>pred</code> (expecting two arguments of the data type to which the
iterators point) returns <code>true</code>, are relocated to the end of the range. The
returned forward iterator marks the beginning of the <a name="an2517"></a>
<em>leftover</em>. For all
pairs of elements in the range <code>[first, return-value)</code> <code>pred</code> returns
<code>false</code> (i.e., are <em>unique</em>), while <code>pred</code> returns <code>true</code> for a
combination of, as its first operand, an element in the range
    <code>[return-value, last)</code> and, as its second operand, an element in the
range <code>[first, return-value)</code>.
            </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;iterator&gt;

    class CaseString
    {
        public:
            bool operator()(std::string const &amp;first,
                            std::string const &amp;second) const
            {
                return !strcasecmp(first.c_str(), second.c_str());
            }
    };

    using namespace std;

    int main()
    {
        string words[] = {"alpha", "alpha", "Alpha", "papa", "quebec" };
        size_t const size = sizeof(words) / sizeof(string);

        string *removed = unique(words, words + size);
        copy(words, removed, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl
             &lt;&lt; "Trailing elements are:\n";
        copy(removed, words + size, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        removed = unique(words, words + size, CaseString());
        copy(words, removed, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl
             &lt;&lt; "Trailing elements are:\n";
        copy(removed, words + size, ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        alpha Alpha papa quebec
        Trailing elements are:
        quebec
        alpha papa quebec
        Trailing elements are:
        quebec quebec
    */
</pre>
    </ul>
<p>
<a name="UNIQUECP"></a><a name="l312"></a>
<h3>17.4.65: unique_copy()</h3>
    <a name="stl/uniquecopy"></a><a name="an2518"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>OutputIterator unique_copy(InputIterator first,
InputIterator last,</code><code>OutputIterator result);</code>
            <li><code>OutputIterator unique_copy(InputIterator first,
InputIterator last,</code><code>OutputIterator Result, BinaryPredicate
pred);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the elements in the range <code>[first,
last)</code> are copied to the resulting container, starting at <code>result</code>.
Consecutively equal elements (using <a name="an2519"></a>
<code>operator==()</code> of the data type to which
the iterators point) are copied only once. The returned output iterator points
just beyond the last copied element.
            <li> The second prototype: the elements in the range <code>[first,
last)</code> are copied to the resulting container, starting at <code>result</code>.
Consecutive elements in the range pointed to by <code>[first, last)</code> for which
the binary predicate <code>pred</code> returns <code>true</code> are copied only once. The
returned output iterator points just beyond the last copied element.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;vector&gt;
    #include &lt;iterator&gt;

    class CaseString
    {
        public:
            bool operator()(std::string const &amp;first,
                            std::string const &amp;second) const
            {
                return !strcasecmp(first.c_str(), second.c_str());
            }
    };

    using namespace std;

    int main()
    {
        string words[] = {"oscar", "Alpha", "alpha", "alpha",
                                                        "papa", "quebec" };
        size_t const size = sizeof(words) / sizeof(string);
        vector&lt;string&gt; remaining;

        unique_copy(words, words + size, back_inserter(remaining));

        copy(remaining.begin(), remaining.end(),
                ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        vector&lt;string&gt; remaining2;

        unique_copy(words, words + size,
                                back_inserter(remaining2), CaseString());

        copy(remaining2.begin(), remaining2.end(),
                ostream_iterator&lt;string&gt;(cout, " "));
        cout &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        oscar Alpha alpha papa quebec
        oscar Alpha papa quebec
    */
</pre>
    </ul>
<p>
<a name="UPPERBOUND"></a><a name="l313"></a>
<h3>17.4.66: upper_bound()</h3>
    <a name="stl/upperbound"></a><a name="an2520"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>ForwardIterator upper_bound(ForwardIterator first,
ForwardIterator last,</code><code>Type const &amp;value);</code>
            <li><code>ForwardIterator upper_bound(ForwardIterator first,
ForwardIterator last,</code><code>Type const &amp;value, Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the sorted elements stored in the
iterator range <code>[first, last)</code> are searched for the first element that is
greater than <code>value</code>. The returned iterator marks the first location in the
sequence where <code>value</code> can be inserted without breaking the sorted order of
the elements, using <a name="an2521"></a>
<code>operator&lt;()</code> of the data type to which the iterators
point. If no such element is found, <code>last</code> is returned.
            <li> The second prototype: the elements implied by the iterator
range <code>[first, last)</code> must have been sorted using the <code>comp</code> function
or function object. Each element in the range is compared to <code>value</code> using
the <code>comp</code> function. An iterator to the first element for which the binary
predicate <code>comp</code>, applied to the elements of the range and <code>value</code>,
returns <code>true</code> is returned.  If no such element is found, <code>last</code> is
returned.
        </ul>
        <li> Example:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;functional&gt;
    #include &lt;iterator&gt;
    using namespace std;

    int main()
    {
        int         ia[] = {10, 15, 15, 20, 30};
        size_t    n = sizeof(ia) / sizeof(int);

        cout &lt;&lt; "Sequence: ";
        copy(ia, ia + n, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        cout &lt;&lt; "15 can be inserted before " &lt;&lt;
                *upper_bound(ia, ia + n, 15) &lt;&lt; endl;
        cout &lt;&lt; "35 can be inserted after " &lt;&lt;
                (upper_bound(ia, ia + n, 35) == ia + n ?
                                    "the last element" : "???") &lt;&lt; endl;

        sort(ia, ia + n, greater&lt;int&gt;());

        cout &lt;&lt; "Sequence: ";
        copy(ia, ia + n, ostream_iterator&lt;int&gt;(cout, " "));
        cout &lt;&lt; endl;

        cout &lt;&lt; "15 can be inserted before " &lt;&lt;
                *upper_bound(ia, ia + n, 15, greater&lt;int&gt;()) &lt;&lt; endl;
        cout &lt;&lt; "35 can be inserted before " &lt;&lt;
                (upper_bound(ia, ia + n, 35, greater&lt;int&gt;()) == ia ?
                                    "the first element " : "???") &lt;&lt; endl;

        return 0;
    }
    /*
        Generated output:

        Sequence: 10 15 15 20 30
        15 can be inserted before 20
        35 can be inserted after the last element
        Sequence: 30 20 15 15 10
        15 can be inserted before 10
        35 can be inserted before the first element
    */
</pre>
    </ul>
<p>
<a name="l314"></a>
<h3>17.4.67: Heap algorithms</h3>
    <a name="stl/heap"></a>A <a name="an2522"></a>
heap is a kind of <a name="an2523"></a>
binary tree which can be represented by an array. In
the standard heap, the key of an element is not smaller than the key of its
children. This kind of heap is called a <a name="an2524"></a>
<em>max heap</em>.  A tree in which
numbers are keys could be organized as shown in figure <a href="cplusplus17.html#heaptree">18</a>.
    <a name="heaptree"></a><p><center><img src="stl/fig/heap.gif" align="bottom" alt="Figure 18 is shown here."/><br>
Figure 18: A binary tree representation of a heap
</center><p><br>

    Such a tree may also be organized in an array:
        <pre>
        12, 11, 10, 8, 9, 7, 6, 1, 2, 4, 3, 5
</pre>
    In the following description, keep two pointers into this array in mind:
a  pointer <code>node</code> indicates the location of the next node of the tree, a
pointer <code>child</code> points to the next element which is a child of the <code>node</code>
pointer. Initially, <code>node</code> points to the first element, and <code>child</code> points
to the second element.
    <ul>
    <li><code>*node++ (== 12)</code>. 12 is the top node. its children are <code>*child++</code>
(11) and <code>*child++</code> (10), both less than 12.
    <li> The next node (<code>*node++ (== 11)</code>), in turn, has <code>*child++</code> (8)
and <code>*child++</code> (9) as its children.
    <li> The next node (<code>*node++ (== 10)</code>) has <code>*child++</code> (7)
and <code>*child++</code> (6) as its children.
    <li> The next node (<code>*node++ (== 8)</code>) has <code>*child++</code> (1)
and <code>*child++</code> (2) as its children.
    <li> Then, node (<code>*node++ (== 9)</code>) has children <code>*child++</code> (4)
and <code>*child++</code> (3).
    <li> Finally (as far as children are concerned) (<code>*node++ (== 7)</code>) has
one child <code>*child++</code> (5)
    </ul>
    Since <code>child</code> now points beyond the array, the remaining nodes have no
children. So, nodes 6, 1, 2, 4, 3 and 5 don't have children.
<p>
Note that the left and right branches are not ordered: 8 is less than 9, but 7
is larger than 6.
<p>
The heap is created by traversing a binary tree level-wise, starting from the
top node. The top node is 12, at the zeroth level. At the first level we find
11 and 10. At the second level 6, 7, 8 and 9 are found, etc.
<p>
Heaps can be created in containers supporting random access. So, a heap is
not, for example, constructed in a list. Heaps can be constructed from an
(unsorted) array (using <a href="cplusplus17.html#MAKEHEAP"><code>make_heap()</code></a>). The top-element can
be pruned from a heap, followed by reordering the heap (using
<a href="cplusplus17.html#POPHEAP"><code>pop_heap()</code></a>), a new element can be added to the heap,
followed by reordering the heap (using <a href="cplusplus17.html#PUSHHEAP"><code>push_heap()</code></a>), and
the elements in a heap can be sorted (using <a href="cplusplus17.html#SORTHEAP"><code>sort_heap()</code></a>,
which invalidates the heap, though).
<p>
The following subsections show the prototypes of the heap-algorithms, the
final subsection provides a small example in which the heap algorithms are
used.
<p>
<a name="MAKEHEAP"></a><a name="l315"></a>
<strong>17.4.67.1: The `make_heap()' function</strong>
        <a name="stl/makeheap"></a><a name="an2525"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>void make_heap(RandomAccessIterator first,
RandomAccessIterator last);</code>
            <li><code>void make_heap(RandomAccessIterator first,
RandomAccessIterator last,</code><code>Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the elements in the range <code>[first,
last)</code> are reordered to form a <a name="an2526"></a>
max-heap, using <a name="an2527"></a>
<code>operator&lt;()</code> of the data
type to which the iterators point.
            <li> The second prototype: the elements in the range <code>[first,
last)</code> are reordered to form a max-heap, using the binary comparison function
object <code>comp</code> to compare elements.
        </ul>
        
        <li> Follow this link for a small <a href="cplusplus17.html#HEAPDEMO">example</a> of a program
using <code>make_heap()</code>.
    </ul>
<p>
<a name="POPHEAP"></a><a name="l316"></a>
<strong>17.4.67.2: The `pop_heap()' function</strong>
        <a name="stl/popheap"></a><a name="an2528"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>void pop_heap(RandomAccessIterator first,
RandomAccessIterator last);</code>
            <li><code>void pop_heap(RandomAccessIterator first,
RandomAccessIterator last,</code><code>Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: the first element in the range
<code>[first, last)</code> is moved to <code>last - 1</code>. Then, the elements in the range
<code>[first, last - 1)</code> are reordered to form a max-heap, using the
<code>operator&lt;()</code> of the data type to which the iterators point.
            <li> The second prototype: the first element in the range
<code>[first, last)</code> is moved to <code>last - 1</code>. Then, the elements in the range
<code>[first, last - 1)</code> are reordered to form a max-heap, using the binary
comparison function object <code>comp</code> to compare elements.
        </ul>
        
        <li> Follow this link for a small <a href="cplusplus17.html#HEAPDEMO">example</a> of a program
using <code>pop_heap()</code>.
    </ul>
<p>
<a name="PUSHHEAP"></a><a name="l317"></a>
<strong>17.4.67.3: The `push_heap()' function</strong>
        <a name="stl/pushheap"></a><a name="an2529"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>void push_heap(RandomAccessIterator first,
RandomAccessIterator last);</code>
            <li><code>void push_heap(RandomAccessIterator first,
RandomAccessIterator last,</code><code>Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: assuming that the range <code>[first,
last - 2)</code> contains a valid heap, and the element at <code>last - 1</code> contains an
element to be added to the heap, the elements in the range <code>[first, last
- 1)</code> are reordered to form a max-heap, using the <code>operator&lt;()</code> of the data
type to which the iterators point.
            <li> The second prototype: assuming that the range <code>[first,
last - 2)</code> contains a valid heap, and the element at <code>last - 1</code> contains an
element to be added to the heap, the elements in the range <code>[first, last
- 1)</code> are reordered to form a max-heap, using the binary comparison function
object <code>comp</code> to compare elements.
        </ul>
        
        <li> Follow this link for a small <a href="cplusplus17.html#HEAPDEMO">example</a> of a program
using <code>push_heap()</code>.
<p>
</ul>
<p>
<a name="SORTHEAP"></a><a name="l318"></a>
<strong>17.4.67.4: The `sort_heap()' function</strong>
        <a name="stl/sortheap"></a><a name="an2530"></a>

    <ul>
        <li> Header file:
        <pre>
        #include &lt;algorithm&gt;
</pre>
        <li> Function prototypes:
        <ul>
            <li><code>void sort_heap(RandomAccessIterator first,
RandomAccessIterator last);</code>
            <li><code>void sort_heap(RandomAccessIterator first,
RandomAccessIterator last,</code><code>Compare comp);</code>
        </ul>
        <li> Description:
        <ul>
            <li> The first prototype: assuming the elements in the range
<code>[first, last)</code> form a valid max-heap, the elements in the range
<code>[first, last)</code> are sorted, using <a name="an2531"></a>
<code>operator&lt;()</code> of the data type to
which the iterators point.
            <li> The second prototype: assuming the elements in the range
<code>[first, last)</code> form a valid heap, the elements in the range
<code>[first, last)</code> are sorted, using the binary comparison function
object <code>comp</code> to compare elements.
        </ul>
        
        <li> Follow this link for a small <a href="cplusplus17.html#HEAPDEMO">example</a> of a program
using <code>sort_heap()</code>.
    </ul>
<p>
<a name="HEAPDEMO"></a><a name="l319"></a>
<strong>17.4.67.5: An example using the heap functions</strong>
        Here is an example showing the various generic algorithms manipulating
            heaps:
        <pre>
    #include &lt;algorithm&gt;
    #include &lt;iostream&gt;
    #include &lt;functional&gt;
    #include &lt;iterator&gt;

    void show(int *ia, char const *header)
    {
        std::cout &lt;&lt; header &lt;&lt; ":\n";
        std::copy(ia, ia + 20, std::ostream_iterator&lt;int&gt;(std::cout, " "));
        std::cout &lt;&lt; std::endl;
    }

    using namespace std;

    int main()
    {
        int ia[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
                    11, 12, 13, 14, 15, 16, 17, 18, 19, 20};

        make_heap(ia, ia + 20);
        show(ia, "The values 1-20 in a max-heap");

        pop_heap(ia, ia + 20);
        show(ia, "Removing the first element (now at the end)");

        push_heap(ia, ia + 20);
        show(ia, "Adding 20 (at the end) to the heap again");

        sort_heap(ia, ia + 20);
        show(ia, "Sorting the elements in the heap");


        make_heap(ia, ia + 20, greater&lt;int&gt;());
        show(ia, "The values 1-20 in a heap, using &gt; (and beyond too)");

        pop_heap(ia, ia + 20, greater&lt;int&gt;());
        show(ia, "Removing the first element (now at the end)");

        push_heap(ia, ia + 20, greater&lt;int&gt;());
        show(ia, "Re-adding the removed element");

        sort_heap(ia, ia + 20, greater&lt;int&gt;());
        show(ia, "Sorting the elements in the heap");

        return 0;
    }
    /*
        Generated output:

        The values 1-20 in a max-heap:
        20 19 15 18 11 13 14 17 9 10 2 12 6 3 7 16 8 4 1 5
        Removing the first element (now at the end):
        19 18 15 17 11 13 14 16 9 10 2 12 6 3 7 5 8 4 1 20
        Adding 20 (at the end) to the heap again:
        20 19 15 17 18 13 14 16 9 11 2 12 6 3 7 5 8 4 1 10
        Sorting the elements in the heap:
        1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
        The values 1-20 in a heap, using &gt; (and beyond too):
        1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
        Removing the first element (now at the end):
        2 4 3 8 5 6 7 16 9 10 11 12 13 14 15 20 17 18 19 1
        Re-adding the removed element:
        1 2 3 8 4 6 7 16 9 5 11 12 13 14 15 20 17 18 19 10
        Sorting the elements in the heap:
        20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
    */
</pre>
<p>

<hr>
<ul>
    <li> <a href="cplusplus.html">Table of Contents</a>
    <li> <a href="cplusplus16.html">Previous Chapter</a>
    <li> <a href="cplusplus18.html">Next Chapter</a>
</ul>
<hr>
</body>
</html>
